sicp习题试解 (2.32)

王朝other·作者佚名 2006-01-09

; ======================================================================

;

; 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:

;; > (subsets (list 1 2 3))

;; (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))