用C语言实现两组数据组合算法

阿贞smile 发布于 2012/02/20 14:16
阅读 2K+
收藏 0

假设有两组数据,上面一组是4个数据,下面一组也是4个数据,如何用C语言实现两组数据的任意组合,但是不能重复。希望大侠们帮小妹解决一下,不胜感激啊

加载中
0
阿贞smile

问题补充:例如:上一组有3个数据1 2 3 ,这组有3个数据4 5 6,他们的组合有6种((1,4)(2,5)(3,6));((1,4)(2,6)(3,5));((1,5)(2,4)(3,6))((1,5)(2,6)(3,4));((1,6)(2,4)(3,5));((1,6)(2,5)(3,4)),

第二组的数据个数可以比第一组的数据多或少,请大侠帮帮忙,

0
翟纯青
翟纯青

我是这样理解的,先不考虑“不能重复”的条件,那么这就是个简单的组合问题,楼主应该可以简单的解决吧?

然后考虑“不能重复”的条件,如果是生成所有组合后再去过滤,不太方便;且当第二组里面如果出现两个或以上的数字与第一组重复,即重新组合会出现重复,去除第二组里这些重复的数据,应该就没问题了。

ps:第一组和第二组如果只有一个重复数字的话,是不影响你的结果的,这点要注意。

 

这是我自己的想法,不知道对不对,你可以试验一下

0
ChenQi
ChenQi

“第二组的数据个数可以比第一组的数据多或少”

感觉和你的例子有矛盾。不然为什么没有( (1,4) (1,5) (1,6) )这种组合?

0
Grrrr
Grrrr

这个题明显就是一个排列组合问题啊. 已知2个数组,长度分别为n,m(n<=m). 那么这两组数据的任意组合数目为: m*(m-1)*(m-2)*......(m-n+1) = A(m,n)

3个和3个组合就是A(3,3) = 6

3个和5个组合就是A(5,3) = 60

4个和1个组合就是A(4,1) = 4

所以一行代码就得到结果了 return(  power(m)/( power(m-n) )  )

阿贞smile
非常感谢,我也是用你的这种思路做的,检测出结果和我需要的是一致的。谢谢啊
0
Grrrr
Grrrr

引用来自“Grrrr”的答案

这个题明显就是一个排列组合问题啊. 已知2个数组,长度分别为n,m(n<=m). 那么这两组数据的任意组合数目为: m*(m-1)*(m-2)*......(m-n+1) = A(m,n)

3个和3个组合就是A(3,3) = 6

3个和5个组合就是A(5,3) = 60

4个和1个组合就是A(4,1) = 4

所以一行代码就得到结果了 return(  power(m)/( power(m-n) )  )

客气客气。其实这个题有一个原型:

将n只小球随机放入N(N>=n)个盒子中去,试求每个盒子之多只有一个球的概率。

p = N(N-1)...(N-n+1)/N的n次方 = A(N,n)/N的n次方。

后来网上有一个延伸的面试题:50个人中至少有2个人生日相同的概率是多少?

0
shewa
shewa

这个代码应该可以的吧。

结果保存在  result.txt 中。你试试吧。

#include<stdio.h>

#include<stdlib.h>

 

 

#define FALSE 10000

void pailie(int * a,int * b,int num,FILE * fp);

 

void printArray(int *a, int len,FILE * fp)

{

for(int i=0;i<len;i++) 

fprintf(fp,"%d ",a[i]);

fprintf(fp,"\n");

}

 

 

void combine(int * a, int alen,int apos,int *b,int blen,int bpos,FILE *fp)

//void combine(int alen,int blen,int *a,int * b,FILE* fp,int apos,int bpos)

{

if(bpos>=blen) printArray(b,blen,fp);

else

for(int  ai=apos; ai<alen; ai++)

{

b[bpos]=a[ai];

//combine(a,a_len,ai+1,b,b_len,b_pos+1);

//combine(alen,blen,a,b,fp,ai+1,bi+1);

combine(a,alen,ai+1,b,blen,bpos+1,fp);

}

}

 

 

 

int liancheng(int n)

{

int res=1;

for(int i=1;i<=n;i++)

res*=i;

return res;

}

int main()

{

 

int numOfFirst,numOfSecond;

int i,j,total;

int * firstArray,*secondArray;

freopen("in.txt","r",stdin);

FILE * fp=fopen("selectNum.txt","w+");

FILE * fresult=fopen("result.txt","w+");

 

printf("input the num of the first array\n");

scanf("%d",&numOfFirst);

firstArray=(int *) malloc(sizeof(int)*numOfFirst);

 

printf("input the %d elements in the first array\n",numOfFirst);

for(i=0;i<numOfFirst;i++)

{

scanf("%d",&firstArray[i]);

 

}

 

printf("input the num of the second  array\n");

scanf("%d",&numOfSecond);

secondArray=(int *) malloc(sizeof(int)*numOfSecond);

 

printf("input the %d elements in the first array\n",numOfSecond);

for(i=0;i<numOfSecond;i++)

{

scanf("%d",&secondArray[i]);

 

}

 

 

if(numOfFirst<numOfSecond)

{

int a,b,c,total;

a=liancheng(numOfSecond);

b=liancheng(numOfSecond-numOfFirst);

c=liancheng(numOfFirst);

// printf("a=%d,b=%d\n",a,b);

total=a/b/c;

 

int * btmp=(int*)malloc(sizeof(int)*numOfFirst);

// printf("total =%d\n",total);

//selectNum(numOfFirst,numOfSecond,secondArray,fp);

combine(secondArray,numOfSecond,0,btmp,numOfFirst,0,fp);

 

fclose(fp);

fp=fopen("selectNum.txt","r");

for(i=0;i<total;i++)

{

for(j=0;j<numOfFirst;j++)

fscanf(fp,"%d",&secondArray[j]);

//                        printf("the second array is \n");

//                        for(j=0;j<numOfFirst;j++)

//                                printf("%d ",secondArray[j]);

//                        printf("\n");

//                // printZuhe(firstArray,secondArray,numOfFirst,fresult);

pailie(firstArray,secondArray,numOfFirst,fresult);

}

}

 

else if(numOfFirst==numOfSecond)

{

total =1;

for(i=0;i<numOfSecond;i++)

fprintf(fp,"%d ",secondArray[i]);

for(i=0;i<total;i++)

{

for(j=0;j<numOfFirst;j++)

fscanf(fp,"%d",&secondArray[j]);

pailie(firstArray,secondArray,numOfFirst,fresult);

}

}

else

{

//select(numOfSecond,numOfFirst,firstArray);

total=liancheng(numOfFirst)/liancheng(numOfFirst-numOfSecond)/liancheng(numOfSecond);

int *btmp=(int *)malloc(sizeof(int)*numOfSecond);

// selectNum(numOfSecond,numOfFirst,firstArray,fp);

combine(firstArray,numOfFirst,0,btmp,numOfSecond,0,fp);

for(i=0;i<total;i++)

{

for(j=0;j<numOfSecond;j++)

fscanf(fp,"%d",&firstArray[j]);

// printZuhe(firstArray,secondArray,numOfFirst,fresult);

pailie(secondArray,firstArray,numOfSecond,fresult);

}

}

 

 

 

}

 

 

void swap (int & a,int & b)

 

{

int c=a;

a=b;

b=c;

}

 

 

void pailie(int * a,int * b,int num,FILE * fp)

{

int i,j,k,x,y;

      do

            for(i=0;i <num;i++)             //输出排列中的数字 

                fprintf(fp,"(%d,%d)",a[i],b[i]);

            fprintf(fp,"\n");

            for( j=num-1;j> 0;j--)       //从右向左;找要交换的位置1(j); 

                  if(b[j]> b[j-1])   break; 

            if(j==0)break;                   //找不到要交换的位置.退出do 

            j--; 

            for(k=num-1;k> j;k--)       //在位置1右边;从右向左; 

                                                //找要交换的位置2(k); 

                  if(b[k]> b[j])break; 

            swap(b[k],b[j]);             //交换位置1和位置2的值; 

            //把位置1后边的所有位反序排列; 

            for(x=j+1,y=num-1;x <y;x++,y--) 

                  swap(b[x],b[y]); 

      }while(1); 

}


阿贞smile
你好,谢谢你提供好的答案,我昨天把问题给解决了,我是把问题给简化之后,一组不变,数据多的一组进行的全排序
0
阿贞smile
非常谢谢各位热心的帮助,使我快速的把问题给解决了。再一次的谢谢你们!
0
彭庆太
彭庆太
觉得排序的组合不止这几种,如何是点坐标集合的话那就又不一样了
返回顶部
顶部