Finding the powerset of a set

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))))

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) ())
> 

Syndicated 2013-11-25 00:00:00 from Ramakrishnan Muthukrishnan