懒洋洋地产生排列
我正在寻找一种算法来生成一个集合的排列，这样我就可以在Clojure中创建一个懒惰列表。 即我想迭代一个排列列表，其中每个排列都不计算，直到我请求它，并且所有排列不必一次存储在内存中。
或者，我正在寻找一种算法，在给定特定集合的情况下，它将返回该集合的“下一个”排列，以这种方式在其自己的输出上反复调用该函数将循环遍历原始集合的所有排列，一些命令（顺序是什么并不重要）。
有没有这样的算法？ 我所见过的大部分排列生成算法倾向于一次生成它们（通常是递归的），它不会扩展到非常大的集合。 在Clojure（或其他函数式语言）中的实现会很有帮助，但我可以从伪代码中找出它。
是的，有一个“下一个排列”算法，它也很简单。 C ++标准模板库（STL）甚至有一个名为next_permutation的函数。
该算法实际上找到下一个排列 - 按字典顺序排列的下一个排列。 想法是这样的：假设你给了一个序列，比如说“32541”。 下一个排列是什么？
如果你仔细想想，你会发现它是“34125”。 你的想法可能是这样的：在“32541”中，
该算法正是为了实现这种推理：
只要前一个元素不小于当前元素，您就可以通过从结尾开始并向后退出来有效地执行（1.）。 你可以通过将“4”替换为“2”来完成（2.），因此你将得到“34521”。一旦你这样做，你可以避免使用（3.）的排序算法，因为尾部是（现在还在考虑这个问题），按降序排列，所以只需要颠倒。
C ++代码正是这样做的（查看系统中/usr/include/c++/4.0.0/bits/stl_algo.h中的源代码，或查看本文）; 将它翻译为您的语言应该很简单：[如果您不熟悉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”，这是下一个排列。
假设我们正在讨论对正在排列的值的字典顺序，可以使用两种常用方法：
n个排列，同时从0向上计数n 。 对于那些不把c ++当作本地语言的人来说，方法1可以通过下面的伪代码来实现，假设从零开始索引为零的数组在索引“左侧”（用其他结构，如列表，“是作为练习留下的”;-)：
1. scan the array from right-to-left (indices descending from N-1 to 0)
1.1. if the current element is less than its right-hand neighbor,
call the current element the pivot,
and stop scanning
1.2. if the left end is reached without finding a pivot,
reverse the array and return
(the permutation was the lexicographically last, so its time to start over)
2. scan the array from right-to-left again,
to find the rightmost element larger than the pivot
(call that one the successor)
3. swap the pivot and the successor
4. reverse the portion of the array to the right of where the pivot was found
5. return
下面是一个以CADB的当前排列开始的例子：
1. scanning from the right finds A as the pivot in position 1
2. scanning again finds B as the successor in position 3
3. swapping pivot and successor gives CBDA
4. reversing everything following position 1 (i.e. positions 2..3) gives CBAD
5. CBAD is the next permutation after CADB
对于第二种方法（直接计算第n个置换），请记住有N! N元素的排列。 因此，如果你正在排列N元素，第一个(N-1)! 排列必须以最小元素开始，下一个(N-1)! 排列必须从第二小排序开始，以此类推。 这导致了下面的递归方法（同样在伪代码中，从0开始编号排列和位置）：
To find permutation x of array A, where A has N elements:
0. if A has one element, return it
1. set p to ( x / (N-1)! ) mod N
2. the desired permutation will be A[p] followed by
permutation ( x mod (N-1)! )
of the elements remaining in A after position p is removed
所以，例如，ABCD的第13个排列如下找到：
perm 13 of ABCD: {p = (13 / 3!) mod 4 = (13 / 6) mod 4 = 2; ABCD[2] = C}
C followed by perm 1 of ABD {because 13 mod 3! = 13 mod 6 = 1}
perm 1 of ABD: {p = (1 / 2!) mod 3 = (1 / 2) mod 2 = 0; ABD[0] = A}
A followed by perm 1 of BD {because 1 mod 2! = 1 mod 2 = 1}
perm 1 of BD: {p = (1 / 1!) mod 2 = (1 / 1) mod 2 = 1; BD[1] = D}
D followed by perm 0 of B {because 1 mod 1! = 1 mod 1 = 0}
B (because there's only one element)
DB
ADB
CADB
顺便说一下，元素的“移除”可以由一个平行的布尔数组表示，表示哪些元素仍然可用，所以不需要在每次递归调用时创建一个新数组。
因此，要遍历ABCD的排列，只需计算0到23（4！-1）并直接计算相应的排列。
你应该检查wikipeda上的Permutations文章。 此外，还有Factoradic数字的概念。
无论如何，数学问题是相当困难的。
在C#您可以使用iterator ，并使用yield停止排列算法。 这个问题是你不能来回或使用index 。