我正在寻找一种算法来生成一组排列，这样我就可以在 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”，这是下一个排列。
假设我们正在讨论置换值的字典顺序，您可以使用两种通用方法：
nth 排列，同时n从 0 向上计数。对于那些（像我一样；-）不说 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
对于第二种方法（直接计算th 排列），请记住元素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 文章。此外，还有阶乘数的概念。
无论如何，数学问题是相当困难的。
在C#您可以使用iterator, 并使用 停止排列算法yield。这样做的问题是你不能来回走动，或者使用index.
更多置换算法的例子来生成它们。
来源：http ://www.ddj.com/architect/201200326
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 J.S. 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;
PROCEDURE WriteArray;
VAR i : INTEGER;
BEGIN
FOR i := 1 TO marksize
DO Write ;
permcount := permcount + 1;
WriteLn;
END;
PROCEDURE LexPerm ;
{ Outputs permutations in lexicographic order. The array marks is global }
{ and has n or fewer marks. The procedure WriteArray () is global and }
{ displays the results. }
VAR
work : INTEGER:
mp, hlen, i : INTEGER;
BEGIN
IF
THEN BEGIN { Swap the pair }
work := marks[1];
marks[1] := marks[2];
marks[2] := work;
WriteArray ;
END
ELSE BEGIN
FOR mp := DOWNTO 1
DO BEGIN
LexPerm<>;
hlen := DIV 2;
FOR i := 1 TO hlen
DO BEGIN { Another swap }
work := marks[i];
marks[i] := marks[n - i];
marks[n - i] := work
END;
work := marks[n]; { More swapping }
marks[n[ := marks[mp];
marks[mp] := work;
WriteArray;
END;
LexPerm<>
END;
END;
BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii;
permcount := 1; { The starting position is permutation }
WriteLn < Starting position: >;
WriteLn
LexPerm ;
WriteLn < PermCount is , permcount>;
ReadLn;
END.
3.
PROGRAM TestAllPerms;
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 AllPerm (n : INTEGER);
{ Outputs permutations in nonlexicographic order. The array marks is }
{ global and has n or few marks. The procedure WriteArray is global and }
{ displays the results. }
VAR
work : INTEGER;
mp, swaptemp : INTEGER;
BEGIN
IF
THEN BEGIN { Swap the pair }
work := marks[1];
marks[1] := marks[2];
marks[2] := work;
WriteArray;
END
ELSE BEGIN
FOR mp := DOWNTO 1
DO BEGIN
ALLPerm<< n - 1>>;
IF >
THEN swaptemp := 1
ELSE swaptemp := mp;
work := marks[n];
marks[n] := marks[swaptemp};
marks[swaptemp} := work;
WriteArray;
AllPerm< n-1 >;
END;
END;
BEGIN { Main }
FOR ii := 1 TO marksize
DO marks[ii] := ii
permcount :=1;
WriteLn < Starting position; >;
WriteLn;
Allperm < marksize>;
WriteLn < Perm count is , permcount>;
ReadLn;
END.
clojure.contrib.lazy_seqs 中的 permutations 函数已经声称可以做到这一点。