SICP 2.32: Generating Power Sets

From SICP section 2.2.2 Hierarchical Structures

Exercise 2.32 introduces the concept of the "set of all subsets" of a given set, which you may recognize from mathematics as the power set. If we have the set S = {x, y, z}, then the power set of S is:

P(S) = { {}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z} }

There are a couple of details to note:

1. The empty set {} is a member of every power set.
2. The original set {x, y, z} is also a member of its own power set.

In Scheme we can represent a set as a list of distinct elements, and the power set as a list of sets. In this exercise, we're given the following definition of a procedure that generates the power set of a set, and asked to complete it:

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

If we're given the set (1 2 3), then the finished procedure should return:

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

If you read the Wikipedia Power set article that I linked to earlier, you'll see that there's a recursive algorithm for calculating power sets (which I'll now quote liberally).

The first step is to define the following operation:


This function takes an element e and a set T, and returns a set with the element e added to each set X in T.

The procedure for generating the power set follows:

If S = {}, the P(S) = {{}} (the set contaning only the empty set) is returned.

Otherwise:

• Let e be any single element of S.
• Let T be the relative complement of {e} in S.
• 

In other words, the power set of the empty set is the set containing the empty set and the power set of any other set is all the subsets of the set containing some specific element and all the subsets of the set not containing that specific element.

This is exactly the same procedure defined in the text. The only part we have to do is finish the initial operation:


The append and map procedures are already doing much of the work for us. We just need to define a function that will add an element e to the set X. The map procedure will apply whatever function we give it to each set in rest (T in the mathematical definition above). We can define that using lambda as follows.

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

Here we're recursively calling subsets with (cdr s), which will append to that the car of s (which represents e from the mathematical definition) to each subset of (cdr s). The recursion stops when we run out of elements and the empty set is returned.

We can test it out with the example given.

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

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.