Powersets II

Table of Contents

1 What

In another article we introduced the power set or poset, which is the collection of all subsets of the set S, and provided one solution. In this article, we provide an alternative solution.

2 Why

The previous solution is straightforward and has good performance characteristics, but it does have the drawback of not taking advantage of the set theory nature of the problem and consequently losing a bit of elegance. This solution improves upon those metrics.

3 How

A simple recursive algorithm is available for generating the power set \(\mathscr{P}(S)\) over the set \(S\). Generate a series of sets of sets \(\mathscr{P}_i\) according to the rule,

\[ \mathscr{P}_0 = \left\{\left\{\right\}\right\} \]

\[ \mathscr{P}_i = \left\{ \forall Q_j \in \mathscr{P}_{i-1}, \forall s_k \in S: Q_j \cup \left\{s_k\right\} \right\} \]

That's quite a mouthful of \(\LaTeX\), and it may be unclear how our lives have been improved by it if at all. Let's break that down by translating it into English. This rule says that the first—or zeroeth—set \(\mathscr{P}_0\) in the series just contains the empty set \(\left\{\right\}\). It also says that every other set \(\mathscr{P}_i\) each contains all the subsets formed by the union of every subset \(Q_j\) in the previous set in the series \(\mathscr{P}_{i-1}\) with every set \(\left\{s_k\right\}\) taken over the set \(S\).

Are you saying that still doesn't help? Perhaps another way to put it is as an algorithm:

  1. Create a new empty list.
  2. Add to that set a new empty list, so that you have a list of lists containing just one element, the empty list.
  3. Loop over our list of lists and for each element \(l_i\) (itself a list),
    1. Loop over our list of original elements and for each element \(s_j\)
    2. add that element \(s_j\) to the list \(l_i\).

Put this way, we have an algorithm that manipulates the list of lists in place. Since sets are generally regarded as immutable (though Python sets do not enforce this), for convenience we switch to simple lists in this algorithm.

Any way you try to explain it in words, it may very well be longer than the actual implementation, whose remarkable concision the reward. We define a single recursive function poset. Its input parameters are items, a set of elements over which we are computing the powerset, and pset, the powerset that has been generated so far. That warrants an explanation.

This function generates the powerset by taking the first element from items and adding it to every set in pset, and then recursively passing to the next function call the remaining elements along with the newly updated powerset. All that remains is to bootstrap the pset list by populating it with a seed set—the empty set—in the first invocation. That's handled easily in Python with a default argument for pset. Within the function, we use standard Python list slicing, list merging, list comprehensions, and the ternary operator to peel apart the items parameter, to compose the updated subsets, to iterate over the elements of items, and to handle the base case.

def poset(items, pset=[[]]):
    return poset(items[1:], pset + [s + items[:1] for s in pset]) if items else pset

That works perfectly. However, for the sake of rigor once again we will adapt our Python lists using the Python frozenset, which is a bona-fide immutable set that can itself be added to other sets.

def poset(items, pset={frozenset({})}):
    items = list(items)
    pset = [list(s) for s in pset]
    return poset(items[1:], pset + [s + items[:1] for s in pset]) if items else {frozenset(s) for s in pset}

Now, we're done! We can use our poset function to generate the power set for any modestly sized set.

print poset([1, 2, 3])
set([frozenset([3]), frozenset([1, 2]), frozenset([]), frozenset([2, 3]), frozenset([1]), frozenset([1, 3]), frozenset([1, 2, 3]), frozenset([2])])

That's not very readable, but if we sacrifice a little rigor by converting the sets back into lists it looks better.

sorted([list(p) for p in poset({1, 2, 3})], key=len)
[[], [3], [1], [2], [1, 2], [2, 3], [1, 3], [1, 2, 3]]

Like with the previous implementation, this was fun. Moreover, it is even more simple and concise. Personally, I think that it's downright elegant!