/*算法说明:
问题:现在有n个球,分别编号为1,2,3···n,对这n个球有多少种不重复的排列,列出所有的排列。
解:由数学知识可知:第一个球有n种选择,第二个球有n-1个选择··所以共有n!种选择(乘法法则)
那么1~n!这n!个整数,每个整数则分别对应不同的组合。
比如现在有3个球,编号为1,2,3,那么可以很容易列出所以的组合为:
123
132
213
231
312
321
其中123这种组合就可以编号为组合1,132这种组合就可以编号为组合2·····,321这种组合就可以编号为组合6,如果要问此时组合4是什么可以很容易查到为:231
那么对于n个球,只要给出一个1~n之间的整数,这个整数就对应着一种组合,那么如何找出这个组合呢,其通用算法又是什么呢?
比方说现在有4个球,问组合16是什么组合的话,可以这样算:
---------
16-1=15
建立一个数组a[0]=1,a[1]=2,a[2]=3,a[3]=4, 然后15/(4-1)!=15/3!=15/6=2```3,商为2,a[2]=3,所以组合的第一个数为a[2]=3
然后将a[2]后面的数都往前面移动,数组变为a[0]=1,a[1]=2,a[2]=4,a[3]=4,余数为3,3/2!=1```1,商为1,a[1]=2,所以组合第二个数为2,然后
数组a[1]后面的数往前移动,数组为a[0]=1,a[1]=4,a[2]=4,a[3]=4,
余数1/1!=1```0,商为1,a[1]=4,所以组合第三个数为a[1]=4,a[1]后面的数字往前移动变为a[0]=1,a[1]=4,a[2]=4,a[3]=4
余数0/0!=0```0,商为0,a[0]=1,所以组合第四个数为1
综合起来为3241
----------
用这种算法可以轻松找出n个球情况下编号为x对应的组合情况*/
#include
#include
#include
int Factorial(int n)//求阶乘函数{
if(n==1) return 1;
else if(n==0) return 1;
else return n*Factorial(n-1);
}
void printout(int index,int n,int *array)//对于n个球,打印出编号为index的排列组合出来{
for(int i=0;i
array[i]=i+1;
}
int divide,left,*out;//divide 为index除某数的商,left为余数 printf("序号:%-3d |",index);
out=(int *)malloc(sizeof(int)*n);//out为用来储存排列排列组合的数组,有n个球所以有n个数 index=index-1;//----------------------------------------------------------- for(i=n-1;i>=0;i--)
{
divide=index/Factorial(i);
left=index%Factorial(i);
out[n-1-i]=array[divide]; //见算法说明 for(int i2=divide;i2
{
array[i2]=array[i2+1];
}
index=left;
}//------------------------------------------------------------------------ for(i=0;i
{
printf("%d",out[i]);//输出排列组合 }
free(out);//释放out占的内存 printf("\n");
}
void main()
{
int n,index=1;
printf("输入球的个数:");
scanf("%d",&n);
int *array;
array=(int*)malloc(sizeof(int)*n);
int fac=Factorial(n);//对于n个球一共有n!种排列组合情况 for(index=1;index<=fac;index++)
{
printout(index,n,array);//每一种排列组合,都有一个对应的编号,对所有编号遍历输出 }
getch();
}