懒洋洋地产生排列
我正在寻找一种algorithm来生成一个集合的排列，这样我就可以在Clojure中创build一个懒惰的列表。 即我想迭代一个排列列表，其中每个排列不被计算，直到我请求它，所有的排列不必一次存储在内存中。
另外，我正在寻找一个给定一个集合的algorithm，它将返回该集合的“下一个”排列，以这种方式重复调用自己的输出函数将循环所有排列的原始集合，在有些命令（顺序是什么并不重要）。
有这样一个algorithm吗？ 我所看到的大部分排列生成algorithm倾向于一次生成它们（通常是recursion的），这不会扩展到很大的集合。 在Clojure（或其他function语言）中的实现将是有益的，但我可以从伪代码中找出它。
是的，有一个“下一个排列”algorithm，它也很简单。 C ++标准模板库（STL）甚至有一个名为next_permutation的函数。
algorithm实际上find下一个排列 – 按字母顺序排列的下一个排列。 这个想法是这样的：假设给你一个序列，比如说“32541”。 下一个排列是什么？
如果你仔细想想，你会发现它是“34125”。 而你的想法可能是这样的：在“32541”中，
- 没有办法保持“32”的固定，并在“541”部分find后面的排列，因为这个排列已经是最后一个5,4，并且它是按照递减sorting的。
- 所以你必须把“2”改成更大的数字 – 实际上是“541”部分的最小数字，即4。
- 现在，一旦你决定排列将以“34”开始，其余的数字应该是递增的，所以答案是“34125”。
该algorithm正是为了实现这种推理：
- 查找按降序排列的最长“尾巴”。 （“541”部分）
- 将尾部（“2”）之前的数字更改为比尾部（4）更大的数字。
- 按升序sorting尾部。
只要前一个元素不小于当前元素，就可以通过开始和结束来有效地执行（1.）。 你可以通过将“4”replace为“2”来完成（2），所以你将得到“34521”。一旦你这样做了，你可以避免使用（3.）的sortingalgorithm，是（现在还在考虑这个），按降序排列，所以只需要颠倒。
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）个时间，但是如果仔细考虑一下，可以certificate总共花费O（n！）个时间，所以只有O（1） – 恒定的时间 – 每个排列。
好的一点是，即使你有一个重复元素的序列，algorithm也能正常工作：比如说“232254421”，它会find尾部为“54421”，交换“2”和“4”（所以“232454221” ），反过来，给出“232412245”，这是下一个排列。
假设我们正在讨论关于正在排列的值的字典顺序，可以使用两种一般方法：
- 将元素的一个排列转换为下一个排列（如ShreevatsaR发布），或者
- 直接计算第
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 (ie positions 2..3) gives CBAD 5. CBAD is the next permutation after CADB
对于第二种方法（直接计算第n个置换），记住有N! N元素的排列。 因此，如果你正在排列N元素，第一个(N-1)! 排列必须以最小的元素开始，下一个(N-1)! 排列必须从第二小sorting开始，以此类推。 这导致了下面的recursion方法（同样在伪代码中，从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
顺便说一下，元素的“去除”可以用一个平行的布尔值数组表示，表示哪些元素仍然可用，所以不需要在每次recursion调用时创build一个新的数组。
因此，要遍历ABCD的排列，只需从0到23（4！-1），直接计算相应的排列。
你应该检查wikipeda上的Permutations文章 。 另外还有Factoradic数字的概念。
无论如何，math问题是相当困难的。
在C#您可以使用iterator ，并使用yield停止排列algorithm。 这个问题是，你不能来回，或使用index 。
置换algorithm的更多例子来生成它们。
来源： http : //www.ddj.com/architect/201200326
- 使用Fikealgorithm，这是已知最快的algorithm之一。
- 使用Algo进行词汇顺序。
- 使用nonlexographic，但运行速度比第2项。
1。
PROGRAM TestFikePerm; CONST marksize = 5; VAR marks : ARRAY [1..marksize] OF INTEGER; ii : INTEGER; permcount : INTEGER; PROCEDURE WriteArray; VAR i : INTEGER; BEGIN FOR i := 1 TO marksize DO Write ; WriteLn; permcount := permcount + 1; END; PROCEDURE FikePerm ; {Outputs permutations in nonlexicographic order. This is Fike.s algorithm} { with tuning by JS Rohl. The array marks[1..marksizn] is global. The } { procedure WriteArray is global and displays the results. This must be} { evoked with FikePerm(2) in the calling procedure.} VAR dn, dk, temp : INTEGER; BEGIN IF THEN BEGIN { swap the pair } WriteArray; temp :=marks[marksize]; FOR dn := DOWNTO 1 DO BEGIN marks[marksize] := marks[dn]; marks [dn] := temp; WriteArray; marks[dn] := marks[marksize] END; marks[marksize] := temp; END {of bottom level sequence } ELSE BEGIN FikePerm; temp := marks[k]; FOR dk := DOWNTO 1 DO BEGIN marks[k] := marks[dk]; marks[dk][ := temp; FikePerm; marks[dk] := marks[k]; END; { of loop on dk } marks[k] := temp;l END { of sequence for other levels } END; { of FikePerm procedure } BEGIN { Main } FOR ii := 1 TO marksize DO marks[ii] := ii; permcount := 0; WriteLn ; WrieLn; FikePerm ; { It always starts with 2 } WriteLn ; ReadLn; END.
2。
PROGRAM TestLexPerms; CONST marksize = 5; VAR marks : ARRAY [1..marksize] OF INTEGER; ii : INTEGER; permcount : INTEGER;
PROGRAM TestLexPerms; CONST marksize = 5; VAR marks : ARRAY [1..marksize] OF INTEGER; ii : INTEGER; permcount : INTEGER;
过程WriteArray;
VAR i：INTEGER;
开始
对于i：= 1来标记
请写;
permcount：= permcount + 1;
WriteLn;
结束;
程序LexPerm;
{以字典顺序输出排列。 数组标记是全局的}
{和有或less或less的标志。 过程WriteArray（）是全局的，}
{显示结果。 }
VAR
工作：整数：
mp，hlen，i：INTEGER;
开始
如果
然后开始{交换对}
工作：=标记[1];
标记[1]：=标记[2];
标记[2]：=工作;
写数组;
结束
ELSE BEGIN
FOR mp：= DOWNTO 1
开始吧
LexPerm <>;
hlen：= DIV 2;
对于我：= 1到hlen
开始{另一个交换}
work：= marks [i];
标记[i]：= marks [n – i];
标记[n – i]：=工作
结束;
工作：=马克[n]; {更多交换}
标记[n [：= marks [mp];
标记[mp]：=工作;
WriteArray;
结束;
LexPerm <>
结束;
结束;
BEGIN {Main}
对于ii：= 1来标记
DO标记[ii]：= ii;
permcount：= 1; {起始位置是排列}
WriteLn <起始位置：>;
WriteLn
LexPerm;
WriteLn <PermCount是，permcount>;
ReadLn;
结束。
3。
PROGRAM TestAllPerms; CONST marksize = 5; VAR marks : ARRAY [1..marksize] of INTEGER; ii : INTEGER; permcount : INTEGER;
PROGRAM TestAllPerms; CONST marksize = 5; VAR marks : ARRAY [1..marksize] of INTEGER; ii : INTEGER; permcount : INTEGER;
过程WriteArray;
VAR i：INTEGER;
开始
对于i：= 1来标记
请写;
WriteLn;
permcount：= permcount + 1;
结束;
过程AllPerm（n：INTEGER）;
{输出nonlexicographic顺序排列。 数组标记是}
{全球和有几个标记。 过程WriteArray是全球性的和}
{显示结果。 }
VAR
工作：INTEGER;
mp，swaptemp：INTEGER;
开始
如果
然后开始{交换对}
工作：=标记[1];
标记[1]：=标记[2];
标记[2]：=工作;
WriteArray;
结束
ELSE BEGIN
FOR mp：= DOWNTO 1
开始吧
ALLPerm << n – 1 >>;
IF>
那么swaptemp：= 1
ELSE swaptemp：= mp;
工作：=马克[n];
marks [n]：= marks [swaptemp};
标记[swaptemp}：= work;
WriteArray;
AllPerm <n-1>;
结束;
结束;
BEGIN {Main}
对于ii：= 1来标记
DO标记[ii]：= ii
permcount：= 1;
WriteLn <起始位置; >;
WriteLn;
Allperm <marksize>;
WriteLn <Perm count，permcount>;
ReadLn;
结束。
clojure.contrib.lazy_seqs中的排列函数已经声称做到这一点。
我在C＃中提供了一个解决scheme，它懒散地产生了这样的排列。
在这里看到我的答案 。
