display | more...
The subsets of a set can be mapped to bit strings, with the bit i being set if the ith element of the set belongs to THAT subset. For consistency, we start counting i from 0. When counting the elements in the set, start counting from the left. When counting the position in the bit string, start counting from the right. Note that none of the things I mention in this paragraph matter - these are just conventions. What is important is consistency. For Example, consider the set (I've indicated the value of i in the second row)
S = { a, b, c, d }
      0  1  3  4
Then the bit string
B = 0010
will correspond to the subset { b } since the second bit is set.

We know that the set of all the subsets of a set contains 2 ^ n sets (if the set has n elements)

So if we generate 2 ^ n bit strings starting from

  • 0 (representing the subset containing none of the elements), and
  • ending in 2 ^ n - 1 (this is a binary number containing n 1's, so it represents the subset that contains all the elements that the original set contains),
then these bit string would represent all the subsets of a set that there are.

And how would we generate these bit strings? Well, each bit string is equivalent to a binary number. Each binary number is also a number. To get the next number from the current one, just add 1 to it. So

subset = 0
last_subset = (2 ** n) - 1
while subset < last_subset
    print bin (subset)
    subset = subset + 1
The above pseudo-code is valid python code (although the bin (subset) might not work in older (< 2.6) versions of python)

Hope I didn't make a mountain out of a molehill.

Log in or register to write something here or to contact authors.