组合算法

最近在看组合数学方面的书籍，看到上面的算法就动笔实现了。

#include <iostream>

using namespace std;
/**求组合数
*(1)找出满足C[i] *i=max{j|C[j] *(2)C[i]=C[i]+1;
*(3)C[j]=C[j-1]+1;j=i+1,i+2,.....
*/
int getMax(int C[],int n,int r){
int k=-1;
for(int i=0;i<r;++i)
if(C[i]<=n-r+i)
k=i;
return k;
}

int Com(int a[],int size,int C[],int r){
int i,num=0;
while((i=getMax(C,size,r))>=0){
for(int k=0;k<r;++k)
cout<<C[k]<<" ";
cout<<endl;
num++;
C[i]=C[i]+1;
for(int j=i+1;j<r;++j)
C[j]=C[j-1]+1;
}
for(int k=0;k<r;++k)
cout<<C[k]<<" ";
cout<<endl;
num++;
return num;
}

int main(){
int a[]={1,2,3,4,5,6};
int r=5,C[r];
for(int i=0;i<r;i++) C[i]=a[i];
int num=Com(a,6,C,r);
cout<<"C(6,"<<r<<")="<<num<<endl;
return 0;
}

编译运行后结果如下：

1 2 3 4 5
1 2 3 4 6
1 2 3 5 6
1 2 4 5 6
1 3 4 5 6
2 3 4 5 6
C(6,5)=6


这个算法需要对数据进行排序。