Creating all possible k combinations of n items in C++

Question

From Rosetta code

#include <algorithm>
#include <iostream>
#include <string>
 
void comb(int N, int K)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's
 
    // print integers and permute bitmask
    do {
        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]) std::cout << " " << i;
        }
        std::cout << std::endl;
    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}
 
int main()
{
    comb(5, 3);
}

output

Analysis and idea

The whole point is to play with the binary representation of numbers
for example the number 7 in binary is 0111

So this binary representation can also be seen as an assignment list as such:

For each bit i if the bit is set (i.e is 1) means the ith item is assigned else not.

Then by simply computing a list of consecutive binary numbers and exploiting the binary representation (which can be very fast) gives an algorithm to compute all combinations of N over k.

The sorting at the end (of some implementations) is not needed. It is just a way to deterministicaly normalize the result, i.e for same numbers (N, K) and same algorithm same order of combinations is returned

For further reading about number representations and their relation to combinations, permutations, power sets (and other interesting stuff), have a look at Combinatorial number system , Factorial number system

PS: You may want to check out my combinatorics framework Abacus which computes many types of combinatorial objects efficiently and its routines (originaly in JavaScript) can be adapted easily to many other languages.

Leave a Comment Cancel reply