首页 > 代码库 > Enumerate Combination C(k, n) in a bitset

Enumerate Combination C(k, n) in a bitset

Suppose n<=32, we can enumerate C(k, n), with bits representing absence or presence, in the following way:

#include <iostream>
#include <vector>
#include <bitset>
using namespace std;

bitset<32> getComb(const vector<int> &comb) {
	bitset<32> bitcombs;
	for (int i=0; i<comb.size(); ++i) bitcombs.set(comb[i], true);
	return bitcombs;
}

bool nextComb(vector<int> &comb, int n) {
	int k = comb.size(), i = k - 1;
	++comb[i];
	while (i>=1 && comb[i]>=n-k+1+i) ++comb[--i];
	if (comb[0] > n-k) return false; 
	for (++i; i<k; ++i) comb[i] = comb[i-1] + 1;
	return true;
}

int main() {
	int n = 3, k = 2;
	vector<int> comb(k);
	for (int i=0; i<k; ++i) comb[i] = i;
	do {
		cout<<getComb(comb).to_ulong()<<endl;
	} while (nextComb(comb, n));
	return 0;
}


The algorithms works like this when k=4, n=5:

01111->10111->11011->11101->11110

So, could you find the pattern?