几种全排列的算法(C语言实现)
/* * 几种排列组合的算法 */#include<stdio.h>int a[20];int n;//打印数组void showArray(int *a){int i;for(i=1;i<=n;i++) printf("%d",a[i]);printf("\n");}//翻转法void overturn(){int i,temp,temp1,temp2,j;int b[20];for(i=1;i<=n;i++)*(b+n-i+1)=*(a+i);showArray(b);for(i=1;i<=n;i++){//判断第一个数是否为1if(i==1 && b[i]!=i){temp=b[i];for(j=1;j<n;j++)b[j]=b[j+1];b[j]=temp;showArray(b);i=0;continue;} //判断第二个数是否为1if(i==2 && b[i]!=i){temp1=b[i];temp2=b[i-1];for(j=1;j+2<=n;j++)b[j]=b[j+2];b[j]=temp1;b[j+1]=temp2;showArray(b);i=0;continue;} //判断第三个数是否为1if(i==3 && b[i]!=i){temp=b[i];temp1=b[i-1];temp2=b[i-2];for(j=1;j+3<=n;j++)b[j]=b[j+3];b[j++]=temp;b[j++]=temp1;b[j]=temp2;showArray(b);i=0;continue;}}}//换位法void changeSite(){int i,temp,temp1;int b[20],max=0;int dir[20]={-1,-1,-1,-1,-1,-1};for(i=1;i<=n;i++)*(b+i)=*(a+i);showArray(b);while(1){max=0;b[max]=0;//寻找最大的活结点 for(i=1;i<=n;i++){ if(i+dir[i]>0 && i+dir[i]<=n && b[i]>b[i+dir[i]])max=b[i]>b[max]?i:max;} if(max==0) break;//交换位置和方向 temp=b[max]; b[max]=b[max+dir[max]]; b[max+dir[max]]=temp;temp1=dir[max+dir[max]];dir[max+dir[max]]=dir[max]; dir[max]=temp1;//改变比活结点大的数的方向 for(i=1;i<=n;i++) if(b[i]>temp) dir[i]=-dir[i]; showArray(b);}}//序数法(排出的序列为有序的)//str:待排序的字符序列 n:首字符下标 len：字符串长度void ordinal(char * str,int n,int len){int i;char temp;if(n==len)puts(str);for(i=n;i<len;i++){temp=str[i];str[i]=str[n];str[n]=temp;ordinal(str,n+1,len);temp=str[i];str[i]=str[n];str[n]=temp;}}void main(){int i;char str[20];for(i=1;i<=4;i++)a[i]=i;a[0]=n=4;printf("对1234这四个数进行全排列\n");printf("翻转法:\n");overturn();printf("换位法:\n");changeSite();printf("序数法:\n");for(i=0;i<n;i++)str[i]=a[i+1]+'0';str[i]=0;ordinal(str,0,n);}?