重学算法-组合(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