算法之字典排序法VIP免费

算法之字典排序法 2

字典序法 字典序法就是按照字典排序的思想逐一产生所有排列

设想要得到由 1,2,3,4 以各种可能次序产生出 4

肯定先排1234, 再排1243, 下来是1324, 1342, …

, 4321

分析这种过程, 看如何由一个排列得到下一个排列, 并给出严格的数学描述

3 设有排列(p) =2763541, 按照字典式排序, 它的下一个排列是

(q) =2764135

(1) 2763541 [找最后一个正序35] (2) 2763541 [找 3 后面比 3 大的最后一个数] (3) 2764531 [交换 3,4 的位置] (4) 2764135 [ 把 4 后面的531 反序排列为 135 即得到最后的排列(q)] 求(p)=p1pi-1pi… pn的下一个排列(q): (1) 求 i=maxj pj-1pj (找最后一个正序) (2) 求 j=maxk pi-1pk(找最后大于 pi-1 者) (3) 互换 pi-1 与 pj 得 p1… pi-2 pj pipi+1pj-1 pi-1 pj+1… pn (4) 反排pj 后面的数得到(q): p1… pi-2 pj pnpj+1pi-1pj-1 …

pi+1 pi 例2

4 设S=1,2,3,4, 用字典序法求出S 的全部排列

解 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321

字典排序法C++代码： #include void repailie(int *a,int n,int dp) {