The text buffewring 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.

Related posts:

1. The GCD and linear combinations
2. Generating multi-subsets using arithmetic

This entry was posted on Tuesday, March 29th, 2005 at 15:28 and is filed under Math, Programming. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.