下面讨论的是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后继续循环枚举当前位置的其他可能取值。 ======================================*/
下面是我自己按照自己的理解做的，其实有点浪费空间了：
#include<stdio.h>
int n,count;//n表示参与排列的数据的个数，count表示不同排列的个数
void fun(int a[],int flag[],int i,int ans[]);
//原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。
//i表示当前对某排列而言，正在寻找到第i个数据。
//ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。
int main()
{
int i;
int a[],flag[],ans[];
freopen("5.out","w",stdout);
scanf("%d",&n);
for(i=;i<n;i++)
{
flag[i]=;
a[i]=i+;
}
count=;
fun(a,flag,,ans);//从第0号开始出发，依次确定每一个位置的数值
printf("total:%d\n",count);
return ;
}
void fun(int a[],int flag[],int i,int ans[])
{
int j,k;
if(i==n-)
{
for(j=;j<n;j++)
{
if(flag[j]==)//找到了一个排列，把这个排列给输出。
{
ans[i]=a[j];
for(k=;k<n;k++) printf("%d ",ans[k]);
printf("\n");
count++;
return ;
}
}
}
else
{
for(j=;j<n;j++)
{
if(flag[j]==)
{
ans[i]=a[j]; flag[j]=;
fun(a,flag,i+,ans);
flag[j]=;
}
}
}
}
-----------------------------------------------------插入分割线-----------------------------------------------------
代码OJ测试：http://ica.openjudge.cn/dg3/solution/10102944/
题目要求：原序列是字母，而且字母不重复，而且原序列按字典序升序排列，要求生成的所有排列按字典序升序输出。
AC代码：（把上面的代码做简单修改即可）
#include<stdio.h>
#include<string.h> int n,count;//n表示参与排列的数据的个数，count表示不同排列的个数
void fun(char a[],int flag[],int i,char ans[]);
//原始数据存放于a[]。flag[]的每一个元素标记a[]对应位置处的元素是否已经被选用。
//i表示当前对某排列而言，正在寻找到第i个数据。
//ans[]是存放每一个排列的地方。每当放够n个元素到ans则开始打印该数组。 int main()
{
int i;
int flag[];
char a[],ans[];
scanf("%s",a);
//scanf("%d",&n);
n=strlen(a);
for(i=;i<n;i++)
{
flag[i]=;
//a[i]=i+1;
}
count=;
fun(a,flag,,ans);//从第0号开始出发，依次确定每一个位置的数值
//printf("total:%d\n",count);
return ;
}
void fun(char a[],int flag[],int i,char ans[])
{
int j,k;
if(i==n)
{
for(k=;k<n;k++) printf("%c",ans[k]);
printf("\n");
count++;
return ;
}
else
{
for(j=;j<n;j++)
{
if(flag[j]==)
{
ans[i]=a[j]; flag[j]=;
fun(a,flag,i+,ans);
flag[j]=;
}
}
}
}
-----------------------------------------------------分割线结束-----------------------------------------------------
下面是书上的代码，比较好一点，不过一开始可能不好理解。建议看懂了上面的再来看这段代码。
#include<stdio.h>
int n,a[];
long count=;
void fun(int k); //fun(k)表示现在正在确定某个排列当中的第k个数
//也可以认为fun(k)是生成第k个数到第n个数的所有排列。
int main()
{
int i;
scanf("%d",&n);
for(i=;i<n;i++)
{
a[i]=i+;
}
fun();
printf("total:%d\n",count);
return ;
}
void fun(int k)//fun(k)表示现在正在确定某个排列当中的第k个数
{
int j,t;
if(k==n)
{
count++;
for(j=;j<n;j++) printf("%d ",a[j]);
printf("\n");
return ;
}
else
{
for(j=k;j<n;j++)//注意：这里是在原始数组内交换数据实现排列，所以j从k开始
{
t=a[k];a[k]=a[j];a[j]=t;
fun(k+);
t=a[k];a[k]=a[j];a[j]=t;
}
}
}
下面是网上对这个问题的代码，也不错。
#include <stdio.h> void print(int array[], int end);
void swap(int &a, int &b);
void permute(int array[], int begin, int end); void permute(int array[], int begin, int end)
{
if (begin == end)
{
print(array, end);
}
else
{
for (int j = begin; j <= end; ++j)
{
swap(array[j], array[begin]);
permute(array, begin+, end); //recursive，enlarge problem's scope
swap(array[j], array[begin]); //backtracking
}
}
return;
} void print(int array[], int end)
{
for (int i = ; i <= end; ++i)
{
fprintf(stdout, "%d", array[i]);
if (i != end)
{
fprintf(stdout, "\t");
}
}
fprintf(stdout, "\n");
return;
} void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
return;
} int main()
{
int array[]={,,,};
permute(array,,);
return ;
}
/*==============================================================================
下面的分析来自王晓东编著的《算法设计与分析（第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()用于交换两个表元素值。
==============================================================================================*/
其实这个算法和上述第二段代码是一个道理。
不管如何修改，采用递归的设计方法实现的全排列，效率都不高。下面看看书上另外写的非递归代码。
（下次再见呵呵）