sicp/2_32.sch

11 lines
415 B
Scheme

(define (subsets s)
(if (null? s)
(list '())
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (l) (cons (car s) l)) rest)))))
; By induction: Empty case is obvious. Suppose we have T_n, the set of subsets of
; S_n = {s_1, ... , s_n}. Let S_{n+1} = S + {s_{n+1}}. Then T_n is a subset of
; T_{n+1}. Any element of T_{n+1}\T_n must contain s_{n+1}, otherwise it would
; have been in T_n.