[求教]组合的算法（C/C++）

组合算法
本程序的思路是开一个数组，其下标表示1到m个数，数组元素的值为1表示其下标
代表的数被选中，为0则没选中。
首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。
然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为
“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的m-n的位置，即n个“1”全部移动到最右端时，就得
到了最后一个组合。
例如求5中选3的组合：
1  1  1  0  0  //1,2,3
1  1  0  1  0  //1,2,4
1  0  1  1  0  //1,3,4
0  1  1  1  0  //2,3,4
1  1  0  0  1  //1,2,5
1  0  1  0  1  //1,3,5
0  1  1  0  1  //2,3,5
1  0  0  1  1  //1,4,5
0  1  0  1  1  //2,4,5
0  0  1  1  1  //3,4,5

程序如下：

#include  "stdio.h"
#include  "time.h"

unsigned  char  number[100];  //最多求100个数的组合。
unsigned  int  m,n;//  2<=m<=100,n<m

char  tmpbuf[128];
time_t  ltime;
struct  tm  *today;

void  printtime(void)  //打印当前时间的函数
{
time(<ime);
today  =  localtime(<ime  );
strftime(tmpbuf,128,"%Y-%m-%d  %H:%M:%S",today);
printf("%s\n",tmpbuf);
}

void  inition()  //初始化
{
unsigned  int  i;
for(i=0;i<n;i++)
number[i]=1;
}

void  output()  //输出组合结果
{
unsigned  int  i;
for(i=0;i<m;i++)
if(number[i])
printf("%02d  ",i+1);
printf("\n");
}

void  main()
{
unsigned  long  count;  //计数组合个数
unsigned  int  i,j,k,l;
bool  findfirst,end,swap;
end=false;
printf("please  input  m:");
scanf("%d",&m);  //输入m
printf("please  input  n:");
scanf("%d",&n);  //输入n
printtime();  //打印开始时间
inition();  //初始化
//output();  //屏蔽掉结果输出以节约时间
count=1;
j=m;
while(!end)
{
findfirst=false;
swap=false;  //标志复位
for(i=0;i<j;i++)
{
if(!findfirst  &&  number[i])
{
k=i;  //k记录下扫描到的第一个数
findfirst=true;  //设置标志
}
if(number[i]  &&  !number[i+1])  //从左到右扫描第一个“10”组合
{
number[i]=0;
number[i+1]=1;
swap=true;  //设置交换标志
for(l=0;l<i-k;l++)
number[l]=number[k+l];
for(l=i-k;l<i;l++)
number[l]=0;  //交换后将之前的“1”全部移动到最左端
if(k==i  &&  i+1==m-n)  //如果第一个“1”已经移动到了m-n的位置，说明
这是最后一个组合了。
end=true;
}
if(swap)  //交换一次后就不用继续找“10”组合了
break;
}
//output();  //屏蔽掉结果输出以节约时间
count++;  //组合数计数器递增1
}
printtime();  //打印结束时间
printf("total  number  of  combination  is:  %d\n",count);  //打印总的组合数

getchar();
}

在vc5.0下编译通过.
在我的p166  16M  RAM机器上算30中选10  的组合，屏蔽掉结果输出花了33秒时间。

---------------------------------------------------------------

全排列算法

从1到N，输出全排列，共N！条。
分析：用N进制的方法吧。设一个N个单元的数组，对第一个单元做加一操作，满N进
一。每加一次一就判断一下各位数组单元有无重复，有则再转回去做加一操作，没
有则说明得到了一个排列方案。
解法一：执行速度：10秒
#include  <stdio.h>
#define  n  5
int  a[n],b[n];
void  swap(int  m)
{
int  b1=b[m];
int  b0=b1;
while(a[b0]>=m){
b0--;
if(b0<0)b0=n-1;
}
int  temp=a[b0];
a[b0]=a[b1];
a[b1]=temp;
int  a0=a[b0];
int  a1=a[b1];
temp=b[a0];
b[a0]=b[a1];
b[a1]=temp;
}
void  output()
{
for(int  j=0;j<n;j++){
printf("%d  ",a[j]);
}
printf("\n");
}
void  permute(int  m)
{
m--;
for(int  i=m;i>=0;i--){
permute(m);
if(i>0){
swap(m);
output();
}
}
}
void  main()
{
for(int  i=0;i<n;i++){
a[i]=b[i]=i;
}
output();
permute(n);
}

解法二：5秒
#  include  <stdio.h>
#  include  <alloc.h>
int  N;
main()
{
int  i,j,k,m,n,*l,*a,m2;
scanf("%d",&N);
if(N<3)
{
puts("N太小!");
exit(1);
}
/*  开数组  */
l=malloc(N*sizeof(int));
a=malloc(N*sizeof(int));
/*  赋初值  */
for(i=0;i<N;i++)
{
a[i]=0;l[i]=i+1;  /*  a[i]-1是第i个元素交换的次数  */
}
m=2;put(l);
do
{
n=l[1];l[1]=l[0];l[0]=n;put(l);  /*  头两个先换一下  */
/*  判断该换哪个了  */
while(a[m-2]  ==  m)
m++;
if(m==N)  break;
/*  下面是整理过程，可能还有办法  */
n=m>>1;
for(i=0,j=m-1;i<n;i++,j--)
{
k=l[i];
l[i]=l[j];
l[j]=k;
}  /*  以上是从小到大重排，下面处理好了可能不必做，因为可以无序
*/
m2=m-2;
a[m2]++;
/*  下面该把第j个和第m个交换  */
j=m-a[m2];
n=l[j];l[j]=l[m];l[m]=n;
put(l);
/*  m以前的重排  */
for(i=0;i<m2;i++)
a[i]=0;
m=2;
}  while(1);
}
put(int  *l)
{
int  i;
for(i=0;i<N;i++)
printf("  %2d",l[i]);
putchar('\n');
}
不用这么麻烦吧，用高中的数列组合公式:
公式1当m!=n：P n m = n*(n-1)(n-2)....(n-m+1)
公式2当m=n : P n m = n! (!n是自然数1到n的阶乘）例如求5中选3的组合:P 5 3 （5在左下角3在左上角）=5*(5-1)*(5-2)*(5-3+1)
5选5的组合:P 5 5 = 5!=120
在用c++中的位移运算，速度更快。

调试易

[求教]组合的算法（C/C++）

解决方案 »