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:

Powerset of *S* = (first element of *S* **U** *x*) **U** *S’* where *S’* = Powerset of {*S* - first element of *S*} and *x* ∈ *S’*

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.

This can be translated to the following racket program

```
#lang racket
;; List -> ListOf List
(define (powerset s)
(if (empty? s)
(list empty)
(let ([ps (powerset (rest s))])
(append (map (λ(l)
(cons (first s) l))
ps)
ps))))
```

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

```
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = ps ++ map ((:) x) ps
where ps = powerset xs
```

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

```
#lang racket
;; List -> ListOf List
(define (powerset s)
(if (empty? s)
(list empty)
(let ([ps (powerset (rest s))])
(append ps (for/list ([x ps])
(cons (first s) x))))))
```

Here is an example:

```
Welcome to DrRacket, version 5.3.6 [3m].
Language: racket; memory limit: 128 MB.
> (powerset '(a c))
'((a c) (a) (c) ())
> (powerset '(a b c))
'((a b c) (a b) (a c) (a) (b c) (b) (c) ())
>
```