全排列输出算法

输出排列算法一、第一种递归算法•假设可以生成n-1个数的全排列，针对n个数的全排列从左至右，第1位可以放入的数据分别是1…n;如此除去第1位放入的数据，后面从第2位到第n位的n-1个数我们由假设是可以输出全排列的；如此既可以得到n个数的全排列方法。VoidPermutations1(intt,int*x){inti;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]);}}}voidOutput(int*x){for(inti=1;i=N;i++)printf(“%d”,x[i]);printf(“\n”);}voidswap(int&a,int&b){intp;p=a;a=b;b=p;}#defineN5voidmain(){intx[N+1];inti=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循环一次都没有被调用因此有﹛0若n=1n*f(n-1)+n若n1f（n）=二、第二种递归算法•假定有办法生成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的全部排列。VoidPermutations2(intm,int*P){inti;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!）；﹛0若m=0m*f(m-1)+n若m0f（m）=三、字典序法字典序法即按照字母出现的顺序先后将字符列的排列全部输出。对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定。例如对于5个数字的排列12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是54321。•字典序算法如下：•23451是数字1…5的一个排列。从它生成下一个排列的步骤如下：自右至左找出排列中第一个比右边数字小的数字4，在该数字后的数字中找出比4大的数中最小的一个5，将5和4交换得到23541，在将41倒序得到23514，所以23451的下一个排列是23514。•字典序法递增进位数制法递减进位数制法邻位交换法n进位制法递归类算法