# Finding the powerset of a set

Posted on 2013-11-25

PowerSet of a set S is a set of all subsets of S. For example, Powerset of `{a, b, c}`

is `{ {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }`

. For any set of length `n`

, the powerset will have a length of `2^n`

.

Writing a program to find the powerset is easy to write, if we can visualize powerset. A simple inductive way to think about it is that the subsets of the set S, either has an element in S or not. We recursively apply this rule, the base case being that the empty set is a subset of S. This can be visualized as a binary tree as shown below.

Members of the powersets are the leaves of this tree. You can now easily come up with a relation:

In other words, take the powerset of S without first element, let us call this set as *S’*. Now, for each of the element *x* in *S’* find the union of the first element with *x*. This is the first part of the power set. The other part involves those that does not have the first element and this is *S’* that we have already computed. The final answer is the set union of first part and second part.

Here is a Haskell version. Pattern matching and the concise syntax makes this definition so elegant.

Or even better, this version uses the Racket list comprehension functions and a more direct translation of our definition of the powerset function: