Pages

Thursday, July 4, 2013

The Subset Problem

There are many variations of this problem, I will stay on the general problem of finding all subsets of a set. For example if our set is [1, 2, 3] - we would have 8 (2 to the power of 3) subsets: {[], [1], [2], [3], [1, 2], [1, 3], [1, 2, 3], [2, 3]}. So basically our algorithm can't be faster than O(2^n) since we need to go through all possible combinations.

There's a few ways of doing this. I'll mention two ways here - the recursive way, that we've been taught in high schools; and using a bit string.

Using a bit string involves some bit manipulation but the final code can be found easy to understand. The idea  is that all the numbers from 0 to 2^n are represented by unique bit strings of n bit width that can be translated into a subset. So for example in the above mentioned array we would have 8 numbers from 0 to 7 inclusive that would have a bit representation that is translated using the bit index as the index of the array.

Nr Bits Combination
0 000 {}
1 001 {1}
2 010 {2}
3 011 {1, 2}
4 100 {3}
5 101 {1, 3}
6 110 {2, 3}
7 111 {1, 2, 3}


It may look easier in the code:


Note:
- The Math.pow call computes 2 to the power of n
- The findLowestBitSet is a method I mentioned earlier. In Java it could look like this:



Or it could be optimized to look like this:


For comparison find below the code for the recursive algorithm:

No comments:

Post a Comment