下面讨论的是n个互不相同的数形成的不同排列的个数。
毕竟，假如n个数当中有相同的数，那n！种排列当中肯定会有一些排列是重复的，这样就是一个不一样的问题了。
/*===================================== 数的全排列问题。将n个数字1，2，…n的所有排列枚举出来。 2 3 1 2 1 3 3 1 2 3 2 1 思路： 递归函数定义如下： void fun(int a[],int flag[],int i,int ans[]); //原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。 //i表示当前对某排列而言，正在寻找到第i个数据。 //ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。 程序中先把原始数据读入到数组a[]。flag[]数组元素全部置0. 生成一个排列的过程可以这样认为： 每次递归都扫描flag[]，寻找一个flag[i]==0然后把a[i]选到排列当中。 （也即放到ans[i]当中。选a[i]后要把flag[i]置1.） 这样就确定了当前排列的第i个元素。 然后递归进入下一层确定第i+1个数。 以此类推，逐层递归直至i==n-1（因为i从0开始，所以是i==n-1）就认为已经得到了一个 完整的排列。这个时候可以把ans数组输出了。 输出后可以开始回溯了。 每次回溯都要把flag[i]置0以便还原现场。（相当于ans[i]不选a[i]了。） 置0后继续循环枚举当前位置的其他可能取值。 ======================================*/
下面是我自己按照自己的理解做的，其实有点浪费空间了：
1 #include<stdio.h> 2 int n,count;//n表示参与排列的数据的个数，count表示不同排列的个数 3 void fun(int a[],int flag[],int i,int ans[]); 4 //原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。 5 //i表示当前对某排列而言，正在寻找到第i个数据。 6 //ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。 7 int main() 8 { 9 int i; 10 int a[20],flag[20],ans[20]; 11 freopen("5.out","w",stdout); 12 scanf("%d",&n); 13 for(i=0;i<n;i++) 14 { 15 flag[i]=0; 16 a[i]=i+1; 17 } 18 count=0; 19 fun(a,flag,0,ans);//从第0号开始出发，依次确定每一个位置的数值 20 printf("total:%d\n",count); 21 return 0; 22 } 23 void fun(int a[],int flag[],int i,int ans[]) 24 { 25 int j,k; 26 if(i==n-1) 27 { 28 for(j=0;j<n;j++) 29 { 30 if(flag[j]==0)//找到了一个排列，把这个排列给输出。 31 { 32 ans[i]=a[j]; 33 for(k=0;k<n;k++) printf("%d ",ans[k]); 34 printf("\n"); 35 count++; 36 return ; 37 } 38 } 39 } 40 else 41 { 42 for(j=0;j<n;j++) 43 { 44 if(flag[j]==0) 45 { 46 ans[i]=a[j]; 47 48 flag[j]=1; 49 fun(a,flag,i+1,ans); 50 flag[j]=0; 51 } 52 } 53 } 54 }
-----------------------------------------------------插入分割线-----------------------------------------------------
代码OJ测试：http://ica.openjudge.cn/dg3/solution/10102944/
题目要求：原序列是字母，而且字母不重复，而且原序列按字典序升序排列，要求生成的所有排列按字典序升序输出。
AC代码：（把上面的代码做简单修改即可）
1 #include<stdio.h> 2 #include<string.h> 3 4 int n,count;//n表示参与排列的数据的个数，count表示不同排列的个数 5 void fun(char a[],int flag[],int i,char ans[]); 6 //原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。 7 //i表示当前对某排列而言，正在寻找到第i个数据。 8 //ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。 9 10 int main() 11 { 12 int i; 13 int flag[20]; 14 char a[20],ans[20]; 15 scanf("%s",a); 16 //scanf("%d",&n); 17 n=strlen(a); 18 for(i=0;i<n;i++) 19 { 20 flag[i]=0; 21 //a[i]=i+1; 22 } 23 count=0; 24 fun(a,flag,0,ans);//从第0号开始出发，依次确定每一个位置的数值 25 //printf("total:%d\n",count); 26 return 0; 27 } 28 void fun(char a[],int flag[],int i,char ans[]) 29 { 30 int j,k; 31 if(i==n) 32 { 33 for(k=0;k<n;k++) printf("%c",ans[k]); 34 printf("\n"); 35 count++; 36 return ; 37 } 38 else 39 { 40 for(j=0;j<n;j++) 41 { 42 if(flag[j]==0) 43 { 44 ans[i]=a[j]; 45 46 flag[j]=1; 47 fun(a,flag,i+1,ans); 48 flag[j]=0; 49 } 50 } 51 } 52 }
-----------------------------------------------------分割线结束-----------------------------------------------------
下面是书上的代码，比较好一点，不过一开始可能不好理解。建议看懂了上面的再来看这段代码。
1 #include<stdio.h> 2 int n,a[20]; 3 long count=0; 4 void fun(int k); //fun(k)表示现在正在确定某个排列当中的第k个数 5 //也可以认为fun(k)是生成第k个数到第n个数的所有排列。 6 int main() 7 { 8 int i; 9 scanf("%d",&n); 10 for(i=0;i<n;i++) 11 { 12 a[i]=i+1; 13 } 14 fun(0); 15 printf("total:%d\n",count); 16 return 0; 17 } 18 void fun(int k)//fun(k)表示现在正在确定某个排列当中的第k个数 19 { 20 int j,t; 21 if(k==n) 22 { 23 count++; 24 for(j=0;j<n;j++) printf("%d ",a[j]); 25 printf("\n"); 26 return ; 27 } 28 else 29 { 30 for(j=k;j<n;j++)//注意：这里是在原始数组内交换数据实现排列，所以j从k开始 31 { 32 t=a[k];a[k]=a[j];a[j]=t; 33 fun(k+1); 34 t=a[k];a[k]=a[j];a[j]=t; 35 } 36 } 37 }
下面是网上对这个问题的代码，也不错。
1 #include <stdio.h> 2 3 void print(int array[], int end); 4 void swap(int &a, int &b); 5 void permute(int array[], int begin, int end); 6 7 void permute(int array[], int begin, int end) 8 { 9 if (begin == end) 10 { 11 print(array, end); 12 } 13 else 14 { 15 for (int j = begin; j <= end; ++j) 16 { 17 swap(array[j], array[begin]); 18 permute(array, begin+1, end); //recursive，enlarge problem's scope 19 swap(array[j], array[begin]); //backtracking 20 } 21 } 22 return; 23 } 24 25 void print(int array[], int end) 26 { 27 for (int i = 0; i <= end; ++i) 28 { 29 fprintf(stdout, "%d", array[i]); 30 if (i != end) 31 { 32 fprintf(stdout, "\t"); 33 } 34 } 35 fprintf(stdout, "\n"); 36 return; 37 } 38 39 void swap(int &a, int &b) 40 { 41 int temp = a; 42 a = b; 43 b = temp; 44 return; 45 } 46 47 int main() 48 { 49 int array[]={1,2,3,4}; 50 permute(array,0,3); 51 return 0; 52 }
/*============================================================================== 下面的分析来自王晓东编著的《算法设计与分析（第2版）》，清华大学出版社出版 ， 第2章递归与分治策略例题2.4排列问题。
设R={r1,r2,r3,...,rn}是要进行排列的n个元素，Ri=R-{ri}。 集合X中的元素的全排列记为perm（X）。（ri）perm（X）表示在全排列perm（X）的每一个 排列前加上前缀ri得到的排列。R的全排列可归纳定义如下： 当n=1时，perm（R）=（r），其中r是集合R中唯一的一个元素。 当n>1时，perm（R）由（r1）perm（R1），（r2）perm（R2），...... ，（rn）perm(Rn)构成。 依此递归定义，可以设计产生perm（R）的递归算法如下： （详见下面代码） ================================================================================*/
public static void perm(Object[] List,int k,int m) {//产生list[k:m]的所有排列 if(k==m) {//只剩一个元素 for(int i=0;i<=m;i++) System.out.print(List[i]); System.out.println(); } else { //还有更多个元素，递归产生排列 for(int i=k;i<=m;i++) { MyMath.swap(List,k,i); perm(List,k+1,m); MyMath.swap(List,k,i); } } }
/*============================================================================================ 算法perm（list，k，m）递归地产生所有前缀是list[0:k-1]且后缀是list[k:m]的全排列的所有排列。
调用算法perm（list,0,n-1）则产生list[0:n-1]的全排列。
在一般情况下，k<m。算法将list[k:m]中每一个元素分别与list[k]中的元素交换，然后递归地计算list[k+1:m]的全排列，
并将结果作为list[0:k]的后缀。
MyMath.swap()用于交换两个表元素值。
==============================================================================================*/
其实这个算法和上述第二段代码是一个道理。
不管如何修改，采用递归的设计方法实现的全排列，效率都不高。下面看看书上另外写的非递归代码。
（下次再见呵呵）