## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.32

## Problem

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

## Solution

Note that all values returned by the procedure `subsets` are lists; the case where
argument `s` is `nil` is a list containing the empty list (which is the
proper set of subsets of the emtpy set), and the case where it's not
is the value generated by applying `append` to two lists.

Here's a complete implementation of this procedure:

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

Test:

(subsets (list 1 2 3))

*Output:*

`
`

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

This implementation is based on the following method of computing subsets. Start with a set *s*,

and a set *t*, identical to *s* save for one additional element,

If is the set of all subsets of *s*, then the set of all
subsets of *t* is the set that contains , plus, for each
set in , an additional set whose elements are all the elements
of that set in plus the element *a*_{n + 1}.

Using the example given above, if the set is

(2 3)

then its set of all subsets is

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

If we add an additional element to the the set,

(1 2 3)

then its set of all subsets is the union of the set of all subsets
of the original set, `(2 3)` and this set of subsets:

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

which is the set of all subsets of `(2 3)` with a new element,
1, added to each.

Note that this method for computing the new set is recursive. To implement it as a procedure
in Scheme, for any given non-empty list (set), divide the list into
two parts, the `car` and the `cdr`. The `car` is the first element of the set (possibly itself a set), and
the `cdr` is a subset of the original set. Find the set of subsets of
the `cdr` by applying the procedure recursively to the `cdr`; this result
is called `rest` in the procedure. Then create a new list (set) whose
elements are formed by `cons`ing the `car` of the original list to each
list (set) in `rest`. This is exactly what the application of `map` does
in the procedure given above. Finally, append this new list to `rest`
to form the set of all subsets of the original list (set).