现有M个不同的号码，想从中随机抽取X种不同的每组N个不同号码的组合。(组合不能重复)
注：N<M。并且X小于M中取N的总排列组合数。要求：有较高的效率。X可能很小，也可能很大。
(千万不要告诉我从M个数随机找N个，然后再与上次生成的组合进行比较……如此，如此，当X值较大时，效率太低)谢谢各位。急
注：N<M。并且X小于M中取N的总排列组合数。要求：有较高的效率。X可能很小，也可能很大。
(千万不要告诉我从M个数随机找N个，然后再与上次生成的组合进行比较……如此，如此，当X值较大时，效率太低)谢谢各位。急
M定义为A[M]取N=3
int i1, i2, i3;
int count = 0;
for ( i1=0; i1<M-2; i1++ ) {
for ( i2=i1+1; i2<M-1; i2++ ) {
for ( i3=i2+1; i3<M; i3++ )
{
//则这里的数组就满足条件
//A[i1]!=A[i2]!=A[i3]
count ++;
}
}
}
即可得到所需要的组合。
其他的类推！
分析：用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');
}
代表的数被选中，为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秒时间。