懒惰地生成排列 [英] Generating permutations lazily

问题描述

我正在寻找一种算法来生成集合的排列，这样我就可以在 Clojure 中制作它们的惰性列表.即，我想遍历一个排列列表，其中每个排列在我请求之前都不会计算，并且所有排列不必一次存储在内存中.

I'm looking for an algorithm to generate permutations of a set in such a way that I could make a lazy list of them in Clojure. i.e. I'd like to iterate over a list of permutations where each permutation is not calculated until I request it, and all of the permutations don't have to be stored in memory at once.

或者，我正在寻找一种算法，在给定某个集合的情况下，它将返回该集合的下一个"排列，以这样的方式重复调用该函数在其自己的输出上将循环遍历原始的所有排列设置，以某种顺序(顺序是什么并不重要).

Alternatively I'm looking for an algorithm where given a certain set, it will return the "next" permutation of that set, in such a way that repeatedly calling the function on its own output will cycle through all permutations of the original set, in some order (what the order is doesn't matter).

有这样的算法吗?我见过的大多数排列生成算法都倾向于一次生成它们(通常是递归的)，这不会扩展到非常大的集合.Clojure(或其他函数式语言)中的实现会有所帮助，但我可以从伪代码中弄清楚.

Is there such an algorithm? Most of the permutation-generating algorithms I've seen tend to generate them all at once (usually recursively), which doesn't scale to very large sets. An implementation in Clojure (or another functional language) would be helpful but I can figure it out from pseudocode.

推荐答案

是的，有一个下一个排列"算法，它也很简单.C++ 标准模板库 (STL) 甚至有一个名为 next_permutation 的函数.

Yes, there is a "next permutation" algorithm, and it's quite simple too. The C++ standard template library (STL) even has a function called next_permutation.

该算法实际上找到了 next 排列——按字典顺序排列的下一个.这个想法是这样的:假设你有一个序列，比如32541".下一个排列是什么?

The algorithm actually finds the next permutation -- the lexicographically next one. The idea is this: suppose you are given a sequence, say "32541". What is the next permutation?

如果你仔细想想，你会发现它是34125".你的想法可能是这样的:在32541"中，

If you think about it, you'll see that it is "34125". And your thoughts were probably something this: In "32541",

• 没有办法保持32"固定并在541"部分找到较晚的排列，因为该排列已经是 5,4 和 1 的最后一个 - 它按降序排序.
• 因此，您必须将2"更改为更大的数字——实际上，更改为比541"部分中的最小数字大，即 4.
• 现在，一旦您决定排列将从34"开始，其余数字应按升序排列，因此答案是34125".

算法就是精确地实现这一推理路线:

The algorithm is to implement precisely that line of reasoning:

1. 找出按降序排列的最长尾巴".(541"部分.)
2. 将尾部之前的数字(2")更改为比尾部大的最小数字(4).
3. 按递增顺序对尾部进行排序.

只要前一个元素不小于当前元素，您就可以通过从末尾开始向后进行有效地执行 (1.).您可以通过将4"与2"交换来完成(2.)，因此您将获得34521".一旦这样做，您就可以避免对(3.)使用排序算法，因为尾部过去和现在(想想这个)都是按降序排列的，所以只需要颠倒即可.

You can do (1.) efficiently by starting at the end and going backwards as long as the previous element is not smaller than the current element. You can do (2.) by just swapping the "4" with the '2", so you'll have "34521". Once you do this, you can avoid using a sorting algorithm for (3.), because the tail was, and is still (think about this), sorted in decreasing order, so it only needs to be reversed.

C++ 代码正是这样做的(查看系统上 /usr/include/c++/4.0.0/bits/stl_algo.h 中的源代码，或查看 这篇文章);将它翻译成您的语言应该很简单:[如果您不熟悉 C++ 迭代器，请将BidirectionalIterator"读作指针".如果没有下一个排列，代码返回 false，即我们已经在降序.]

The C++ code does precisely this (look at the source in /usr/include/c++/4.0.0/bits/stl_algo.h on your system, or see this article); it should be simple to translate it to your language: [Read "BidirectionalIterator" as "pointer", if you're unfamiliar with C++ iterators. The code returns false if there is no next permutation, i.e. we are already in decreasing order.]

template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
                      BidirectionalIterator last) {
    if (first == last) return false;
    BidirectionalIterator i = first;
    ++i;
    if (i == last) return false;
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i--;
        if (*i <*ii) {
            BidirectionalIterator j = last;
            while (!(*i <*--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if (i == first) {
            reverse(first, last);
            return false;
        }
    }
}

看起来每个排列可能需要 O(n) 时间，但是如果您仔细考虑一下，您可以证明所有排列总共需要 O(n!) 时间，因此只需 O(1) -- 恒定时间 -- 每排列.

It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes O(n!) time for all permutations in total, so only O(1) -- constant time -- per permutation.

好消息是，即使您有一个包含重复元素的序列，该算法也能正常工作:例如，使用232254421"，它会发现尾部为54421"，交换2"和4"(所以"232454221")，把剩下的倒过来，得到"232412245"，这是下一个排列.

The good thing is that the algorithm works even when you have a sequence with repeated elements: with, say, "232254421", it would find the tail as "54421", swap the "2" and "4" (so "232454221"), reverse the rest, giving "232412245", which is the next permutation.

这篇关于懒惰地生成排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！