Power Set - Algorithms

Algorithms

If is a finite set, there is a recursive algorithm to calculate .

Define the operation

In English, return the set with the element added to each set in .

• If ,then is returned.
• Otherwise:

• Let be any single element of .
• Let, where '' denotes the relative complement of in .
• And the result: is returned.

In other words, the power set of the empty set is the set containing the empty set and the power set of any other set is all the subsets of the set containing some specific element and all the subsets of the set not containing that specific element.

There are other more efficient ways to calculate the power set. For example, use a list of the n elements of S to fix a mapping from the bit positions of n-bit numbers to those elements; then with a simple loop run through all the 2n numbers representable with n bits, and for each contribute the subset of S corresponding to the bits that are set (to 1) in the number. When n exceeds the word-length of the computer (typically 64 in modern CPUs) the representation is naturally extended by using an array of words instead of a single word.