全排列输出算法.pptVIP

输出排列算法 一、第一种递归算法 假设可以生成 n-1个数的全排列，针对n个数的全排列从左至右，第1位可以放入的数据分别是1…n;如此除去第1位 放入的数 据，后面从第2位到第n位的n-1 个数 我们由假设是可以输出全排列的；如 此既可以得到n 个数的全排列方法。 Void Permutations1(int t,int *x) { ??????int i; ????? if(t==N) ?????? { ???????????Output(x); ?????? } ?????? else ?????? { ????????????for(i=t;i=N;i++) ????????????{ ?????????????????swap(x[t],x[i]); ???????????????? Permutations1 (t+1,x); ?????????????????swap(x[i],x[t]); ?????? ?} ?????? } } void Output(int *x) {?for(int i=1;i=N;i++) printf(“%d ”,x[i]); printf(“\n”); } void swap(int a,int b) {?int p;?p=a;?a=b;?b=p; } #define N 5 void main() { ?int x[N+1]; int i=0; ?for(i=1;i=N;i++)? x[i]=i;? Permutations1 (1,x); ?} 时间复杂度 O（nn!）； 当t=1时，for循环被执行了N次，permutation1（2）被调用了N次；当N=1时for循环一次都没有被调用 因此有 ﹛ 二、第二种递归算法 假定有办法生成1、2、3、…n-1的全排列算法，那就能扩展生成1…n的全排列算法，把1、2、…n-1放入数组P[2..n],把n 放入P[1],把数组P[2..n]全排列输 出；接下来n放入P[2],将其他的n-1项 子式全排列输出。这样一次将n放入下 一个数组项里，输出其他子式的全排 列。最后可以输出1…n的全部排列。 Void Permutations2(int m,int *P) { ??????int i; ????? if(m==0) Output(P); ??????else ??????{ ??????????for(i=1;i=n;i++) ??????????{ ???????????????if(P[j]==0){ P[j]=m; ?????????????? Permutations2(m-1,P); ??????????????? P[j]=0; ? }????? } ????? } } 时间复杂度 O（nn!）； ﹛ 三、字典序法 字典序算法如下： 23451是数字1…5的一个排列。从它生成下一个排列的步骤如下：  自右至左找出排列中第一个比右边数字小的数字4 ，在该数字后的数字中找出比4大的数中最小的一个5，将5和4交换得到 23541，在将41倒序得到23514 ，所 以23451的下一个排列是23514 。 字典序法 递增进位数制法 递减进位数制法 邻位交换法 n进位制法 递归类算法 * * 0 若n=1 n*f(n-1) +n 若 n1 f（n）= 0 若m=0 m*f(m-1) +n 若 m0 f（m）= 字典序法即按照字母出现的顺序先后将字符列的排列全部输出。 对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列 中最前面的是12345，最后面的是 54321。 * *