乐正

Actions speak louder than words.

Sicp-ex2-32

问题

我们可以将一个集合表示为一个元素互不相同的表,因此就可以将一个集合的所有子表表示 为表的表。例如,假定集合(1 2 3),它的所有子集的集合就是(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))。 请完成下面的过程定义,它生成出一个集合的所有子集的集合。请解释它为什么能完成这一 工作。

1
2
3
4
(define (subsets s)
  (if (null? s) (list)
      (let ((rest (subsets (cdr s))))
        (append rest (map <??> rest)))))

解答

练习2.32 (ex2-32.scm) download
1
2
3
4
5
6
7
8
;; Happy hacking Yuez - Emacs ♥ you!

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

上面的代码运算逻辑如下:

  • 将集合$s$除去第一个元素first的集合的子集rest,加上
  • firstrest中的每个元素组成的集合

整体思路和1.2.2节中的换零钱方式统计很像。

测试

1
2
(subsets (list 1 2 3))
;Value 17: (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

draft

« sicp-ex2-31 sicp-ex2-33 »

Comments