Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1073548
  • 博文数量: 77
  • 博客积分: 11498
  • 博客等级: 上将
  • 技术积分: 1840
  • 用 户 组: 普通用户
  • 注册时间: 2006-05-04 11:10
文章分类

全部博文(77)

文章存档

2011年(1)

2010年(16)

2009年(5)

2008年(55)

分类: C/C++

2008-10-13 21:17:43


    组合算法注记
    作者:tyc611.cublog.cn,2008-10-13

计算一个集合的组合,最直观的方式是使用递归:首先选择一个元素,然后在剩下的集合中选择其余元素。代码实现也很简单,下面的代码计算集合的所有可能的组合(一个或多个元素):
#include
#include
#include
#include
using namespace std;

template
void CalcCombination(const ElemType elements[], int num, int k, vector &pre)
{
    assert(k <= num);
   
    if (k == 0) {
        // output one combination
        copy(pre.begin(), pre.end(), ostream_iterator(cout, " "));
        cout << endl;
        return;
    }
   
    for (int i = 0; i <= num - k; ++i) {
        pre.push_back(elements[i]);
        CalcCombination(elements + i + 1, num - i - 1, k - 1, pre);
        pre.pop_back();
    }
}

template
void CalcCombination(const ElemType elements[], int num)
{
    vector one;
    for (int i = 1; i <= num; ++i)
        CalcCombination(elements, num, i, one);
}

int main()
{
    char elements[] = {'a', 'b', 'c', 'd'};
    const int NUM = sizeof(elements) / sizeof(elements[0]);
    CalcCombination(elements, NUM);
}

运行结果:
a
b
c
d
a b
a c
a d
b c
b d
c d
a b c
a b d
a c d
b c d
a b c d

另外,还可以使用位运算来实现组合计算。对于元素个数为n的集合,可以使用n位来表示每一个元素,位1表示该元素被选中,位0表示该位未被选中。那么,计算组合C(n, k)就相当于计算出n位数中有k个1位的所有数,每一个计算出的数就表示一个选中的组合。例如,下面的代码可计算最多32个元素的C(n,k)组合(如果需要用此方法计算更多元素的组合,则需要使用更多位数的数来表示组合):
#include
#include
using namespace std;

typedef unsigned int uint32_t;

// 输出数表示的组合
template
void OutputCombination(const T elements[], int num, uint32_t combinationBits)
{
    for (int i = 0; i < num; ++i) {
        if (combinationBits & uint32_t(1) << i)
            cout << elements[i];
    }
    cout << endl;
}

// 产生跟pre有相同的1位,且比pre大的下一个数,如果不存在,返回0
uint32_t NextCombination(uint32_t pre)
{
    uint32_t lastOne = pre & -pre;
    uint32_t high = pre + lastOne;
   
    if (high == 0)
        return 0; // 已经达到最大值
   
    uint32_t mid = high ^ pre;
    uint32_t low = (mid >> 2) / lastOne;
    return high | low;
}

template
void GenAllCombination(const T elements[], int num, int k)
{
    assert(1 <= num && num <= 32 && 1 <= k && k <= num);
   
    // 产生最小的具有k个1的数
    uint32_t number = (uint32_t(1) << k) - 1;
    // 具有k个1的最大的num位数
    uint32_t maxNumber = number << (num - k);
   
    for (; true; number = NextCombination(number)) {
        OutputCombination(elements, num, number);
        if (number == maxNumber)
            break;
    }
}

int main()
{
    const int NUM = 5;
    char elements[NUM];
   
    for (int i = 0; i < NUM; ++i)
        elements[i] = 'a' + i;
   
    GenAllCombination(elements, NUM, 2);
}

程序运行结果如下:
ab
ac
bc
ad
bd
cd
ae
be
ce
de


阅读(1583) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2009-09-22 18:04:53

呵呵,发现这里有许多的好东西啊。准备都看一遍~~ 你的代码风格也是很不错啊。赞! 学习中……