Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
31 lines (24 sloc) 1.2 KB
(define nil '())
(define (subsets s)
(if (null? s)
(list nil)
(let ((rest (subsets (cdr s))))
(append rest (map
(lambda (x)
(cons (car s) x))
rest)))))
;;; 使用例
(subsets '()) ; (())
(subsets '(1)) ; (() (1))
(subsets '(2)) ; (() (2))
;;; リストサイズが2以上の場合、display で結果を表示する
(subsets '(1 2)) ; (() #0=(2) (1) (1 . #0#))
(display (subsets '(1 2))) ; (() (2) (1) (1 2))
(subsets '(1 2 3)) ; (() #0=(3) #1=(2) #2=(2 . #0#) (1) (1 . #0#) (1 . #1#) (1 . #2#))
(display (subsets '(1 2 3))) ; (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
;;; うまくいく理由
;;; ある集合のすべての部分集合は、
;;; その集合から1要素を取り除いた集合のすべての部分集合(xとする)と、
;;; x の各要素(部分集合)に対して、取り除いた要素を足して作った集合から得られる。
;;;
;;; 定義した subsets はこのプロセスを表現しているため、うまく計算することができる。