《2022年算法之字典排序法归类 .pdf》由会员分享，可在线阅读，更多相关《2022年算法之字典排序法归类 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法之字典排序法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) 276
2、4135 把 4 后面的 531反序排列为135 即得到最后的排列 (q) 求(p)=p1pi-1pipn的下一个排列 (q): (1) 求 i=max j pj-1pj(找最后一个正序 ) (2) 求 j=max k pi-1pk(找最后大于 pi-1者) (3) 互换 pi-1与 pj得p1pi-2 pj pipi+1pj-1 pi-1 pj+1pn(4) 反排 pj后面的数得到 (q): p1pi-2 pj pnpj+1pi-1pj-1 .pi+1 pi 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -
3、 - - - - - 第 1 页，共 6 页 - - - - - - - - - 例 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 intn-dp;
4、 int *cc=new intn-dp; int ti=0; for(int i=dp+1;in;i+) bbti+=ai; for(int j=0;jti;j+) aj+dp+1=bbti-j-1; /coutadp+1 ; /coutendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - int main(void) int n; cout请输入 1 至无穷大的数 n; int *a=new intn; int p=1
5、;/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; /coutp ; for (int i=0;in;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - ai=i+1; coutai ; coutendl; while(q=0;j-) if(a
6、j-1aj) b=aj-1; bi=j-1; c=aj; ci=j; break; /coutbi ci =0;k-) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - if (akb) d=ak; di=k; break; /coutdiendl; for(int l=0;ln;l+) if(l=di) al=b; /coutalendl; if(l=bi) al=d; /coutalendl; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - repailie(a,n,bi); for (int m=0;mn;m+) coutam ; coutendl; +q; 运行结果图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -