算法之字典排序法VIP免费

算法之字典排序法 2. 字典序法 字典序法就是按照字典排序的思想逐一产生所有排列. 设想要得到由 1,2,3,4 以各种可能次序产生出 4!个“单词”. 肯定先排1234, 再排1243, 下来是1324, 1342, … ., 4321. 分析这种过程, 看如何由一个排列得到下一个排列, 并给出严格的数学描述. 例 2.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) { int *bb=new int[n-dp]; int *cc=new int[n-dp]; int ti=0; for(int i=dp+1;i>n; int *a=new int[n]; int p=1;//n 的阶层 int q=1;//循环记录 int b,c;//最后一对正序 int bi,ci;//记录b 和 c 的位置 int d;//最后大于 b 者 int di;//记录d 的位置 for (int o=1;o<=n;o++) { p=p*o; //cout<=0;j--) { if(a[j-1]=0;k--) { if (a[k]>b) { d=a[k]; di=k; break; } } //cout<