TA貢獻2051條經(jīng)驗 獲得超10個贊
假設我們在討論排列值的字典順序，則可以使用兩種通用方法：
將元素的一個排列轉換為下一個排列（如ShreevatsaR發(fā)布），或者
從0向上n計數(shù)n，直接計算th排列。
對于那些不像本地人那樣講c ++的人（如我；-），可以從下面的偽代碼實現(xiàn)方法1，假設索引的零從零開始在索引的左側為數(shù)組（用其他結構代替） ，例如列表，是“作為練習留下的；”-）：
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
因此，例如，發(fā)現(xiàn)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
順便說一下，元素的“刪除”可以由布爾值的并行數(shù)組表示，該數(shù)組指示哪些元素仍然可用，因此不必在每個遞歸調(diào)用上創(chuàng)建新的數(shù)組。
因此，要遍歷ABCD的排列，只需從0到23（4！-1）計數(shù)并直接計算對應的排列即可。
舉報