理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

問題2-32

集合のべき集合を求めます。

(define (map proc items)
  (if (null? items)
      ()
      (cons (proc (car items))
	    (map proc (cdr items)))))

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

あんまし意味ないけど、こうやってもできるよ。

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

結果。

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