Next: 16.5 集合族の同等性
Up: 16 集合
Previous: 16.3 集合の同等性
べき集合(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日