设当前排列为P1 P2 ,…,Pn,则下一个排列可按如下算法完成:
1.求满足关系式Pj-1 < Pj 的 j 的最大值,设为i,即
i=max{ j | Pj-1 < Pj , j = 2..n}
2.求满足关系式Pi-1 < Pk的 k 的最大值,设为j,即
j=max{K | Pi-1 < Pk , k = 1..n}
3.Pi -1与Pj互换得 (P) = P1 P2 ,…,Pn
4.(P) = P1 P2 ,…, Pi-1 Pi,…, Pn部分的顺序逆转,得P1 P2 ,…, Pi-1 Pn Pn-1,…, Pi便是下一个排列。
例:设P1 P2 P3 P4 =3421
1 .i= max{j | Pj-1 < Pj , j = 2..n} = 2
2 .j=max{k| Pi-1 < Pk , k =1..n} = 2
3 .P1 与P2 交换得到4321
4 .4321 的321 部分逆转得到4123 即是3421 的下一个排列。
当然,最汗的是 c++ next_permutation 可以直接获得 仰慕c++。。。。