Sunday, June 7, 2009

Ex-2.32

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

Why it works?
Wishful thinking :)
we assumed that we got subsets of (cdr s), now all we need to think is how to get additional subsets of s that contain (car s) and the answer is simply to include (car s) in all the subsets of (cdr s).

No comments:

Post a Comment