如何历遍所有的N!排列
比如
123
132
213
231
312
321
把这种所有的组合历遍出来,如何设计算法~?
[解决办法]
全排列算法，搜索即可。
搜了一个递归的：
#include <stdio.h>
int mm=0;
void permutation(char a[], int m, int n)
{
int i;
char t;
if (m <n-1)
{
permutation(a, m+1, n);
for (i=m+1;i <n;i++)
{
t=a[m];
a[m]=a[i];
a[i]=t;
permutation(a, m+1, n);
t=a[m];
a[m]=a[i];
a[i]=t;
}
}
else
{
printf( "%sn ", a);
mm++;
}
}
int main()
{
char a[]= "12345 ";
permutation(a, 0,5);
printf( "%d ",mm);
return 0;
}
设计思路：
//设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}
//(ri)Perm(X)表示在全排列Perm(X)的每一个排列前加上前缀ri得到的排列
//
// (1)当n=1时，Perm(R)=(r),其中r是集合R中唯一的元素；
// (2)当n> 1时，Perm(R)可由(r1)Perm(R1),(r2)Perm(R2),…,(rn)Perm(Rn)构成
//
//此程序就是按照上述思想来设计的
//
//其中：
// Perm(list,k,m)递归地产生所有前缀是list[0:k-1],且后缀是list[k:m]的全排列的所有排列。那么调用算法Perm(list,0,n-1)则产生list[0:n-1]的全排列。
//
// for (i=k; i <= n; i++) {
// Swap (list[k], list[i]);
// Perm (list, k+1, n);
// Swap (list [k], list [i]);
// }
//以上这段代码其实就是实现的(2)的思想。
[解决办法]
//这不是组合啊，是排列。
//既然是排列就没有什么最好的方法，直接用循环。
//递归之类的费时间也费空间。
int main()
{int i,j,k;
for(i=1;i <=3;i++)
{ for(j=1;j <=3;j++)
{ for(k=1;k <=3;k++)
{printf( "%d ",i);
printf( "%d ",j);
printf( "%d\n ",k);
}
}
}
return 0;
}
[解决办法]
建议去学习下组合数学，个人感觉S.Even给出的算法应该是最容易实现的
[解决办法]
这好像是pku上的一道题，以前好像在上面做过
可以上去看一看
