SICP exercise 2.32

From Drewiki

Jump to: navigation, search

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: 

 

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: 

 

Test: 

 

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,

s : \left \{ a_1, a_2, a_3, \dots a_n \right \}

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

t : \left \{ a_1, a_2, a_3, \dots a_n, a_{n+1} \right \}

If s\prime is the set of all subsets of s, then the set of all subsets of t is the set that contains s\prime, plus, for each set in s\prime, an additional set whose elements are all the elements of that set in s\prime plus the element an + 1.

Using the example given above, if the set is 

 

then its set of all subsets is 

 

If we add an additional element to the the set, 

 

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: 

 

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

Retrieved from "http://wiki.drewhess.com/wiki/SICP_exercise_2.32"
Personal tools