; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 07/28/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.2.32
(define (subsets s)
(if (null? s)
(list ())
(let ((rest (subsets (cdr s))))
(append rest (map (lambda (x) (cons (car s) x)) rest)))))
;; 一个集合S的子集为：
;; *) 当S为空集， 其唯一的子集是空集
;; *) 当S至少有一个元素，即S可表示为某个元素e和剩余元素集合S'= S -{e}, 此时
;; S的子集 = 不含有元素e的S的子集 + 含有元素e的S的子集
;; 显然， 1) 不含有元素e的S的子集就是S'的子集
;; 2) 对于任何一个不含有e的S的子集，存在一个含有e的S的子集；反之亦然。
;; 即在含有e的S的子集和不含有e的S的子集存在一个一一对应的关系。
;; 由此， S的子集 = S'的子集 + {z | x是S'的任何一个子集 -> z = x + {e}}
;; 对应到程序中：
;; S的子集： (subsets s)
;; e： (car s)
;; S'： (cdr s)
;; S'的子集： (subsets (cdr s)) ---> rest
;; 因此 (subsets s) = rest + map (x -> {e}+x) rest
;; Test-it:
;; Welcome to MzScheme version 209, Copyright (c) 2004 PLT Scheme, Inc.
;; > (subsets (list 1 2 3))
;; (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
