我正在尋找一種算法來生成集合的排列，以便可以在Clojure中列出它們的惰性列表。即，我想遍歷一系列排列，在我請求之前不會計算每個排列，并且不必將所有排列立即存儲在內存中。或者，我正在尋找一種算法，給定特定集合，該算法將返回該集合的“下一個”排列，以這種方式，在其自己的輸出上重復調用該函數將循環遍歷原始集合的所有排列，一些訂單（順序無關緊要）。有這樣的算法嗎？我見過的大多數排列生成算法都傾向于一次全部生成它們（通常是遞歸生成），而這些算法并不能擴展到非常大的集合。用Clojure（或另一種功能語言）實現將很有幫助，但我可以從偽代碼中弄清楚。
3 回答
侃侃無極
TA貢獻2051條經驗 獲得超10個贊
假設我們在討論排列值的字典順序，則可以使用兩種通用方法：
將元素的一個排列轉換為下一個排列（如ShreevatsaR發布），或者
從0向上n計數n，直接計算th排列。
對于那些不像本地人那樣講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
對于第二種方法（直接計算nth排列），請記住存在元素的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）計數并直接計算對應的排列即可。
添加回答
舉報
0/150
提交
取消