SICP 問題 2.32（部分集合を求める）
【問題】
集合は相異なる要素のリストで表現できる。また、集合の全ての部分集合の集合を、リストのリストで表現できる。例えば集合が
の時、全ての部分集合の集合は、
(1 2 3)
である。集合の部分集合の集合を作り出す手続きの次の定義を完成し、なぜうまく行くか、明解に説明せよ。
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3) )
(define (subsets s) (if (null? s) (list '()) (let ((rest (subsets (cdr s)))) (append rest (map <??> rest)))))
【解答】
いや〜、とっかかりがわからなくて時間かかっちゃった。
ヒントは正規評価順序で展開してみることだった。というわけで、やってみよう。
サンプルとして使用するデータは (1 2 3) にする。
また、提示されている の箇所は、おそらく s が必要になると思われるので、
仮に次のように定義したとして考えていく。
(define (subsets s) (if (null? s) (list '()) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (x) s) rest)))))
lambda の引数 x が全然関係なくなっちゃってるけどとりあえずこれでヨシ。
じゃ、さっそく正規順序で展開していってみよ〜。
;------------------------------ (subsets '(1 2 3)) ;------------------------------ (let ((rest (subsets (cdr '(1 2 3))))) (append rest (map (lambda (x) '(1 2 3)) rest))) ;------------------------------ (let ((rest (subsets '(2 3)))) (append rest (map (lambda (x) '(1 2 3)) rest))) ;------------------------------ (let ((rest (let ((rest (subsets (cdr '(2 3))))) (append rest (map (lambda (x) '(2 3)) rest))))) (append rest (map (lambda (x) '(1 2 3)) rest))) ;------------------------------ (let ((rest (let ((rest (subsets '(3)))) (append rest (map (lambda (x) '(2 3)) rest))))) (append rest (map (lambda (x) '(1 2 3)) rest))) ;------------------------------ (let ((rest (let ((rest (let ((rest (subsets (cdr '(3))))) (append rest (map (lambda (x) '(3)) rest))))) (append rest (map (lambda (x) '(2 3)) rest))))) (append rest (map (lambda (x) '(1 2 3)) rest))) ;------------------------------ (let ((rest (let ((rest (let ((rest (subsets '()))) (append rest (map (lambda (x) '(3)) rest))))) (append rest (map (lambda (x) '(2 3)) rest))))) (append rest (map (lambda (x) '(1 2 3)) rest))) ;------------------------------ (let ((rest (let ((rest (let ((rest (subsets '()))) (append rest (map (lambda (x) '(3)) rest))))) (append rest (map (lambda (x) '(2 3)) rest))))) (append rest (map (lambda (x) '(1 2 3)) rest)))
さて、ここまでで一通り展開ができた。こっから収束していくわけだ。
少しづつすすめてみよう。
;------------------------------ (let ((rest (let ((rest (let ((rest '(()))) (append rest (map (lambda (x) '(3)) rest))))) (append rest (map (lambda (x) '(2 3)) rest))))) (append rest (map (lambda (x) '(1 2 3)) rest))) ;------------------------------ (let ((rest (let ((rest (append '(()) (map (lambda (x) '(3)) '(()))))) (append rest (map (lambda (x) '(2 3)) rest))))) (append rest (map (lambda (x) '(1 2 3)) rest)))
ここで、実際の lambda の手続きが評価されるようになるわけだが、
(append '(()) (map (lambda (x) '(3)) '(())))
について更に詳しく見てみる。
appendだから、この式が評価されると、
(() ??）
になるわけだが、問題文の評価結果を見ると??にくるべきはどうやら (3) だ。
ならば、
(map (lambda (x) '(3)) '(()))
が (3) になるようにするには本当はどうすればよいか、と考えると、
(map (lambda (x) (cons (car '(3)) x)) '(()))
こんな感じ？ちょっとこの式だけ評価してみよう。
よしよし。入れ子になっててちょっと「？」と思ったけど、よくよく考えたら「(3)」が連結したい要素になるんだからこれでOK。じゃ、appendも評価してみよう。
gosh> (map (lambda (x) (cons (car '(3)) x)) '(()))
((3)）
gosh>
いいね〜♪じゃ、lambda の式を上記のように書き換えた定義を改めて書いてみる。
gosh> (append '(()) (map (lambda (x) (cons (car '(3) ) x) ) '(())))
(() (3) ）
gosh>
(define (subsets s) (if (null? s) (list '()) (let ((rest (subsets (cdr s)))) (append rest (map (lambda (x) (cons (car s) x)) rest)))))
では実験。問題で採用されているテストデータ (1 2 3) を使ってみる。
同一のポインタを指し示している表記になっているのでちょっと見づらい。
gosh> (subsets '(1 2 3))
(() #0=(3) #1=(2) #2=(2 . #0#) (1) (1 . #0#) (1 . #1#) (1 . #2#)）
gosh>
print を使って出力させてみよう。
うむ。予想した通りになってるね。
(print (subsets '(1 2 3)))
(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)）
#
gosh>
で、問題は lambda のを定義することと、もう一つ「なぜうまくいくか」についても答えなきゃならんのだが、アルゴリズム的にうまくいっている理由は上手に説明できないなぁ。
print 使う前の同一性の情報を含めた出力結果を見ると、何が起きてるのかは分かるんだけど。。
（各要素、1 2 3 は最小の部分集合で、それらの総当たりの組み合わせで部分集合が生成されていることが分かる。）
う〜む。とりあえずこれでヨシにしよう。。
