懒惰地产生排列 [英] 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.
算法实际上找到下一个排列 - 字典词典下一个。想法是这样的：假设你给了一个序列，说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:
- 找到以递减顺序排序的最长的尾。 （541部分。）
- 将尾部（2）之前的数字更改为尾部（4）中的最小数字。
- 以递增顺序对尾部进行排序。
只要前一元素不小于当前元素，则向后和向后。你可以通过将4与2交换来做（2），所以你会有34521。一旦你这样做，你可以避免使用排序算法
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 中，或参阅这篇文章）;它应该很容易翻译成你的语言：[阅读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屋！
