8 Dec 2013 rkrishnan   » (Journeyer)

Finding the powerset of a set

Posted on November 25, 2013 by rkrishnan

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 xS’

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

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

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!