# Powersets II

## 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:

- Create a new empty list.
- Add to that set a new empty list, so that you have a list of lists containing just one element, the empty list.
- Loop over our list of lists and for each element \(l_i\) (itself a
list),
- Loop over our list of original elements and for each element \(s_j\)
- 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*!