計算機プログラムの構造と解釈　第二版 P65 問題2.32

sicp

こんな問題は簡単だ。(と思っていたら難しかった。)
受験勉強的には。


要は、穴埋め問題なんだけど、

(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map rest)))))

の<??>って部分を埋めて、

(1 2 3)

って集合から、すべての部分集合の集合

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

が出るようにすればいい。


ふんぬ。わらわせるぜ。(受験勉強的には)


ここでドラゴン桜的には、
・の中には何か手続き(lambda)がはいる。
・(cdr s)っていうのがあるから、たぶん、(car s)はここで使うだろう。
・たぶん、consかlistかappendでリストをつなげるような関数になるだろう。


って言う予測は何となく立てられる。
そんでまーためしてみる。まずはconsで試してみましょう。
の中にこんな感じのをいれてみる。

(lambda (x) (cons (car s) x))

そしたら、一発でいけた。


でも、こういうやり方でやると、実際、人気者になれない。
おかげで僕は(間借りさせてもらっている)社内でつまはじきものにされ、発言権を失い。
窓際に追いやられ、現在では雀の数を数えるだけの毎日だ。
まさに世紀末。


まーいい。やり方はいろいろある。
僕が勤めてる会社(が間借りさせてもらっている会社)には、
異常に頭がいい人がいる。(id:ajiyoshi)
彼は猫好きで、僕は猫アレルギーだが特に問題は生じない。


ということで彼の解説を僕流の咀嚼で書いてみると。

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

上のリストから3が入っている部分だけくりぬいてみる。
そうすると

A
 (() (2) (1) (1 2))

と

B
 ((3) (2 3) (1 3) (1 2 3))

すると何か法則性があるよね。
Aの各要素に、3をconsしてやった結果が、Bの各要素になってる。
そして、AとBをappendしてやった集合が、求める答えだ。


これでもまだ納得しない小僧は次にAを2のはいっている部分だけでくりぬいてみるといい。

A1
 (() (1))

と

A2
 ((2) (1 2))

A1の各要素に、2をconsしてやった結果が、A2の各要素になってる。
そして、A1とA2をappendしてやった集合が、求める答えだ。


まるでデジャブを見ているように繰り替えされているこの構造！！


実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-
(define nil '())

(define myaggregate (list 1 2 3)) 

(define (func x)
  (display x)) 

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


;; main
(define (main args)

  (display "myaggregate: ")
  (display myaggregate)
  (newline)

  (display "(subsets myaggregate): ")
  (display (subsets myaggregate))
  (newline)

  0)


実行

myaggregate: (1 2 3)
(subsets myaggregate): (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

できた！！