Listing All Subsets

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

Lets try out the algorithm for the set S=\{a,b\}.

The subsets are \{\}, \{b\}, \{a\}, \{a,b\}.

Now look at the numbers 0, 1, 2, 3 in binary: 00, 01, 10, 11.

We can say that 00 represents the set \{\}, 01 the set \{a\}, 10 the set \{b\} and 11 the set \{a,b\}. 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 S is included in the subset.

This does mean we need an ordering for the set S. 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 S.

1. Create an array, A, of all the numbers from 0 to 2^{|S|}  - 1.

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

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

Thats it. Happy coding.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s