Serendip

Web Studio

問題2.32

subsets が 引数s の全ての部分集合のリストを返すとすると、rest は s の先頭要素を除いた集合の全ての部分集合のリスト。
s の全ての部分集合のリストは、rest と rest の各要素に s の先頭要素を追加したものとの合成となる。

gauche での表示の為に print を使って表示している。

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

(print (subsets (list 1 2 3)))

(subsets '())         ;=> (())
(subsets '(3))        ;=> (() (3))
(subsets '(2 3))      ;=> (() (3) (2) (2 3))
(subsets '(1 2 3))    ;=> (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る