sicp-ex-2.32



<< Previous exercise (2.31) | Index | Next exercise (2.33) >>


jz

This would be a tough problem in other languages, but it's really terse in Scheme. The hard part is the logic, but it's pretty clear when you get your head around it.

The set of all subsets of a given set is the union of:

Example 1: given the set (3), the first bullet gives the subset (), and the second bullet gives (), (3).

Example 2: given the set (2, 3), the first bullet gives the subsets () and (3). The second bullet gives (2), (2, 3), (), and (3). Note that the first two subsets are the same as the last two subsets with 2 unioned into each subset.

Note this logic is similar to the coin-counting problem in section 1.2.2.

  
 (define nil '()) 
  
 (define (subsets s) 
   (if (null? s) 
       (list nil)   ;; initially had nil, always got () back! 
       (let ((rest (subsets (cdr s)))) 
         (append rest (map (lambda (x) (cons (car s) x)) rest))))) 
  
 (subsets (list 1 2 3)) 
 (subsets (list 1 2 3 4 5)) 
  
  

This problem becomes easy when you evolve the process manually:

(subsets '(1 2 3))
rest ← (subsets '(2 3))
       rest ← (subsets '(3))
              rest ← (subsets '())
                     '(())
              (append '(()) (map ⟨…⟩ '(())))
              '(() (3))
       (append '(() (3)) (map ⟨…⟩ '(() (3))))
       '(() (3) (2) (2 3))
(append '(() (3) (2) (2 3)) (map ⟨…⟩ '(() (3) (2) (2 3))))
'(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

The problem now is to find the function (λ (x)) to map, which has the characteristics:

'(())               ⟼ '((3))                     given s = '(3)
'(() (3))           ⟼ '((2) (2 3))               given s = '(2 3)
'(() (3) (2) (2 3)) ⟼ '((1) (1 3) (1 2) (1 2 3)) given s = '(1 2 3)

Which is plainly the result of prepending the first item of S to each sublist X; that is, to cons the car of S onto each sublist. In Scheme parlance, (λ (x) (cons (car s) x).