全排列字典序生成算法

由某個排列“P1P2…Pn”生成的next permutation的算法如下:

以求839647521的下一個排列為例

1. 确定i，從左到右兩兩比較找出後一個數比前一個大的組合，在這裡有“39” “47”，然後i取這些組中最到的位置号（不是最大的數）。例：在這兩個組合中7的位置号最大為6，是以i=6
2. 确定l，在i（包括i）後面的序列中，從右向左找出比i-1大的第一個數，記下位置号為l。例：在此例中從右向左第一個比4大的數為5，則選5的位置号為7，是以l=7
3. Pi-1 <->Pl後得到P1P2…Pi-1 (P i….Pn ) ,将括号内部分轉置,得到下一個排列。例：先将4和5交換，然後将5後的四位數倒轉得到結果：839657421 –》 839651247