exercise-32.scm (3231B)
1 ;; Exercise 2.32 2 3 (define (exercise-2.32) 4 (define (subsets s) 5 (if (null? s) 6 (list '()) 7 (let ([rest (subsets (cdr s))]) 8 (append rest 9 (map (lambda (x) 10 (cons (car s) 11 x)) 12 rest))))) 13 14 (subsets '()) 15 (if (null? '()) 16 (list '()) 17 (let ([rest (subsets (cdr s))]) 18 (append rest 19 (map (lambda (x) 20 (cons (car s) 21 x)) 22 rest)))) 23 (list '()) 24 25 (subsets '(1)) 26 (if (null? '(1)) 27 (list '()) 28 (let ([rest (subsets (cdr '(1)))]) 29 (append rest 30 (map (lambda (x) 31 (cons (car '(1)) 32 x)) 33 rest)))) 34 (let ([rest (subsets (cdr '(1)))]) 35 (append rest 36 (map (lambda (x) 37 (cons (car '(1)) 38 x)) 39 rest))) 40 (let ([rest (subsets '())]) 41 (append rest 42 (map (lambda (x) 43 (cons (car '(1)) 44 x)) 45 rest))) 46 (append '(()) 47 (map (lambda (x) 48 (cons 1 x)) 49 '(()))) 50 (append '(()) 51 (list (cons 1 '()))) 52 (append (list '()) 53 (list (list 1))) 54 (list '() (list 1)) 55 56 ;; We go deep into the list each time we [rest (subset (cdr s))]. 57 ;; The first rest we really get is '(). 58 ;; Then we append (list rest) to (map ... rest). 59 ;; (map ... rest) is (map ... '()), so it's '(). 60 ;; (list rest) is '(()), so we append '(()) to '(), 61 ;; which is '(()). We return that to the above procedure call 62 ;; and now rest is '(()). 63 ;; We append '(()) to (map ... '(())). 64 ;; This time we map over a non-empty list, so the map proc 65 ;; is important. It is (map (lambda (x) (cons (car s) x)) rest). 66 ;; That is, we attach the current first element of s to each of 67 ;; the elements of rest. Because this is done from the last to first 68 ;; items of s in the subsets call stack, we first cons the last element 69 ;; first while unwinding the callstack. 70 ;; (map ... rest) is (list (cons (car s) '())), so (map ...) 71 ;; is (list (list s-item-n)). rest is '(()), so attaching 72 ;; '(()) to (list s-item-n) is (list '() (list s-item-n)). 73 ;; We return that and assign to rest. 74 ;; Now rest is (list '() (list s-item-n)). 75 ;; We attach (list '() (list s-item-n)) to 76 ;; (list (list s-item-n-1) (list s-item-n-1 s-item-n)) 77 ;; thereby getting (list '() (list s-item-n) (list s-item-n-1) (list s-item-n-1 s-item-n)) 78 ;; and we see the pattern. Each time we go up the call stack we append the previous combinations, 79 ;; rest, to the list where s-item-i was consed to each of the elements of rest. 80 ;; So at each point we append the list, rest, where s-item-i did not appear to the list 81 ;; where it did appear and return that. 82 ;; In the end we get all combinations of subsets where any particular s-item-i appared and all 83 ;; combinations of subsets where s-item-i did not appear. 84 85 (test-begin "2.32") 86 (test-equal 87 '(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)) 88 (subsets '(1 2 3))) 89 (test-end "2.32")) 90 91 (exercise-2.32)