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.


comments powered by Disqus