SICP solution exercise 2.32

Solution for exercise 2.32 of SICP:

(define nil '())

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

(define a (list ))
(define b (list 1 2 3))
(define c (list 1 2 3 4))

;;; tests
(subsets a)
(subsets b)
(subsets c)

;;; explanation
; The set of all subsets consists of the subsets that contain 
; the car of the original set and those subsets that don't 
;(the latter being called rest).
; By recursively appending the rest and combinations of the car 
; and the distinct elements of the rest we get the complete set
; of all subsets.
This entry was posted in SICP and tagged , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>