Listing All Subsets

A common problem in discrete math is listing all subsets for a given set say There’s a trivial recursive algorithm for listing all subsets but I want to give an algorithm for listing subsets when is small.

Lets try out the algorithm for the set

The subsets are

Now look at the numbers 0, 1, 2, 3 in binary:

We can say that 00 represents the set , 01 the set , 10 the set and 11 the set . Remember to read the binary numbers from right to left. Given a binary number the set it represents corresponds to the one’s in the binary number, so if the binary number has a one in the 10th bit (where the 10th bit is the 10 character from the right end of the number) than the 10th element in the set is included in the subset.

This does mean we need an ordering for the set But the ordering is only used when listing out the subsets so it’s doesn’t violate the condition that sets aren’t ordered (if we wanted to list the subsets of an infinite set this could be a problem).

Now it’s obvious how to list the subsets of a set

1. Create an array, A, of all the numbers from 0 to

2. Iterate over the array A and for each element, n, of A list out the corresponding subset of If n = 1 then the corresponding subset is where

Use bitwise arithmetic to retrieve the individual bits from a number. For getting the n^th bit from a number, x, in java, c, etc. do “x & pow(2,n)”. If x has a 1 in the n^th then “x & pow(2,n) == 2ⁿ” otherwise it’s == 0.

_{Thats it. Happy coding.}