重學算法-組合(Combination)

1.背景

上一篇介紹了枚舉排列元組的方法，本篇介紹枚舉組合元組的方法。上一篇介紹的枚舉排列元組的方法實際是枚舉的P(n,n)的元組，而不是通用的P(n,r)。但是本篇介紹完枚舉組合元組C(n,r)的方法后，就可以根據公式P(n,r)=C(n,r)*P(r,r)很容易地實現枚舉P(n,r)排列元組的方法了。

2.算法步驟

假定有0,1,...,n-1這些元素，枚舉C(n,r)的元組。
（1）把組成組合的前r個元素從小到大排列，這當作組合的第一個元組。
0,1,...,r-1
（2）從后向前搜索當前元組中的元素，發現第一個位置，如果此位置的元素還小于最大值，則把此位置的元素的值加1。此新元組是需要的元組。把此位置用i表示，則此位置的最大值為n-r+i-1。
（3）對i位置后的元素，后面的元素是前面的元素加1。
（4）如果（2）能夠構造新的元組則從（1）繼續。否則結束。

3.算法代碼

#include?<stdio.h>

#define?MAX?100

typedef?void?OutProc(int?[],int);

//output
void?OutputCombination(int?ary[],int?n)
...{
????static?int?count=0;
????int?i;
????printf("%05d?:?",++count);
????for(i=0;i<n;i++)
????...{????????
????????printf("%d?",ary[i]);
????}
????printf(" /n");
}

//main?algorithms
void?Combination(int?n,int?r,OutProc?proc)
...{
????int?ary[MAX];
????int?i,k;
????for(i=0;i<r;i++)?ary[i]=i;
????proc(ary,r);
????bool?finished=false;
????while(!finished)
????...{
????????finished=true;
????????for(i=r-1;i>=0;i--)
????????...{
????????????if(ary[i]<i+n-r)
????????????...{
????????????????ary[i]++;
????????????????finished=false;
????????????????for(k=i+1;k<r;k++)
????????????????...{
????????????????????ary[k]=ary[k-1]+1;
????????????????}
????????????????proc(ary,r);
????????????????break;
????????????}
????????}
????}
}

//test
void?combination_test()
...{
????Combination(5,3,OutputCombination);
}

//main
int?main()
...{
????combination_test();
????return?0;
}

4.運行結果

00001?:?0?1?2
00002?:?0?1?3
00003?:?0?1?4
00004?:?0?2?3
00005?:?0?2?4
00006?:?0?3?4
00007?:?1?2?3
00008?:?1?2?4
00009?:?1?3?4
00010?:?2?3?4

總結

以上是生活随笔為你收集整理的组合(Combination)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。