Eli Bendersky's website The text buffering widget I'm building allows the user to apply filters to the text. A need arose to combine various filters, say given 3 filters, each combination is also a filter (i.e. filter 1 and 2 are active, filters 2 and 3 are active, etc.)
Given the basic filters, to compute the combinations one runs into an interesting problem: given a set S={a,b,c} find all combinations of its members.
In mathematical terms this is called a power set of S - namely, the set of all subsets of S. In our case, the power set of S is:
{}, {a}, {b}, {c}, {a,c}, {a,b}, {b,c}, {a,b,c}
So, given the set S as a vector in C++ I need to generate another vector - the power set.
Fortunately, arithmetic in binary base gives us a very nice way to enumerate the subsets.
Given a set size N, consider the binary representation of the numbers 0..N-1:
000, 001, 010, 011, 100, 101, 110, 111
If we think of 0 as "not included" and 1 as "included" we get exactly the power set.
So, in C++ it's a simple matter of looping all the numbers between 0 and N-1, and for each one check the inclusion of each set member - if the bit at place X is set, the Xth element is in the next set, etc.