SICP Exercise 2.32: Power Sets

We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)). Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))

We have a recursive procedure here:

• If we have the empty set then the complete set of subsets is the empty set.
• Otherwise, in order to build the complete set of subsets for the set we:
  1. First build the complete set of subsets for the set with its first item removed.
  2. Then we map this list of subsets in some way.
  3. Finally we join these two sets together (via append) to produce the complete set of subsets.

So what's the mapping step? Well, we can define the complete set of subsets of any non-empty set s as being the union of two sets:

1. The set of all subsets of s that do not include the head of s.
2. The set of all subsets of s that do include the head of s.

Now if we have a complete implementation of subsets, then the local variable rest will contain the first of these sets. We can produce the second of these sets by noting that the first and second sets have the same number of elements, and that each element in the second set can be produced by taking an element from the first set and adding the head of s to it. Note that this is a pretty common algorithm for producing power sets, which is what this procedure is meant to be doing.

Okay, so here's how we complete the procedure:

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (x) (cons (car s) x)) rest)))))

And let's give it a spin:

> (subsets (list 1 2))
'(() (2) (1) (1 2))
> (subsets (list 1 2 3))
'(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
> (subsets (list 1 2 3 4))
'(() (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4) (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4)
 (1 2 3) (1 2 3 4))

The discussion above also indicates why this is a correct approach. Let's go a step further and give a proof by induction for the algorithm.

First we show that the base case is correct: that the power set of the empty set contains only one set, the empty set:

  (subsets nil)
= (if (null? nil)
      (list nil)
      (let ((rest (subsets (cdr nil))))
        (append rest (map (lambda (x) (cons (car nil) x)) rest)))))
= (if #t
      (list nil)
      (let ((rest (subsets (cdr nil))))
        (append rest (map (lambda (x) (cons (car nil) x)) rest)))))
= (list nil)
= (())

Before we move onto the inductive step, let's make the observation that, given that rest is the set of all subsets of s that do not include the head of s, then (map (lambda (x) (cons (car s) x)) rest) will append the head of s onto each of these subsets and so produce the set of all subsets of s that do include the head of s.

Now onto the inductive step. Given the assumption that for any arbitrary set s, (subsets s) correctly produces the power set of s, we need to prove that (subsets (cons h s)) produces the power set of (cons h s):

  (subsets (cons h s))
= (if (null? (cons h s))
      (list nil)
      (let ((rest (subsets (cdr (cons h s)))))
        (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))))
= (if #f
      (list nil)
      (let ((rest (subsets (cdr (cons h s)))))
        (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))))
= (let ((rest (subsets (cdr (cons h s)))))
    (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))
= (let ((rest (subsets s)))
    (append rest (map (lambda (x) (cons (car (cons h s)) x)) rest)))
= (append (subsets s) (map (lambda (x) (cons h x)) (subsets s)))

Now we know that (subsets s) is the set of all subsets of (cons h s) that do not include h. We also know from our previous observation that (map (lambda (x) (cons h x)) (subsets s)) produces the set of all subsets of (cons h s) that do include h. Therefore appending these two sets together produces the set of all subsets of (cons h s).