组合算法注记
作者: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) |