next up previous
Next: 16.5 集合族の同等性 Up: 16 集合 Previous: 16.3 集合の同等性

16.4 巾集合(power set)

べき集合(power set)は, 集合Aの部分集合全体からなる集合のことをいう. たとえば,(1 2 3)のべき集合は,

(nil (1) (2) (3) (1 2) (2 3) (1 3) (1 2 3))
という形になる. 定義は,たとえば,
(defun power-set (set)
  (cond
      ((null set) (list nil))
    (t (append
        (power-set (cdr set))
        (power-set-aux
         (car set)
         (power-set (cdr set)))))))

(defun power-set-aux (e sets)
  (mapcar* #'(lambda (s) (cons e s)) sets))
という形で定義すれば,
> (power-set '(a b))
(nil (b) (a) (a b))
> (power-set '(1 2 3))
(nil (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))
> (power-set '(1 2 3 4))
(nil (4) (3) (3 4) (2) (2 4) (2 3) (2 3 4)
 (1) (1 4) (1 3) (1 3 4) (1 2) (1 2 4)
 (1 2 3) (1 2 3 4))
という形になる.

generated through LaTeX2HTML. M.Inaba 平成18年5月7日