algorithm - 懒惰地生成排列

Question

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

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

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

Answer 1

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

该算法实际上找到了下一个 排列——按字典顺序排列的下一个排列。这个想法是这样的:假设给你一个序列，比如“32541”。下一个排列是什么？

如果您考虑一下，您会发现它是“34125”。而你的想法可能是这样的:在“32541”中，

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

该算法将精确地实现推理线:

1. 找到以降序排列的最长“尾部”。 (“541”部分。)
2. 将尾部之前的数字(“2”)更改为比尾部中的数字大的最小数字(4)。
3. 按升序对尾部进行排序。

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

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

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 ) -- 恒定时间 -- 每个排列。

好处是，即使你有一个包含重复元素的序列，该算法也能正常工作:比如，“232254421”，它会发现尾部为“54421”，交换“2”和“4”(所以"232454221")，反转其余部分，得到 "232412245"，这是下一个排列。