4.2 同値類の生成

Next: 4.3 集合から同値類を作る関数 Up: 4 例題：同値類の計算 Previous: 4.1 同値関係・同値類

4.2 同値類の生成

集合とグラフに関連して同値類(equivalent classes)というものをここで取り上げておきます．たとえば，

> (eq-classes '((a b) (d e) (b c) (f e)))
((C A B) (F D E))

というように，辺の集合を与えると辺で結ばれた頂点のリストの集合が返るような関数を考えます．前回までに取り扱ってきたグラフは連結なグラフであったため，


>(eq-classes '((s a) (s d) (a b) (a d)
                  (b c) (b e) (d e) (e f)))
((F E C B D S A))

という具合に，頂点のリストがひとつになって返ります．


(defun eq-classes (x)
  (cond
   ((null x) nil)
   (t (eq-classes-aux (car x)
        (eq-classes (cdr x))))))

(defun eq-classes-aux (a b)
  (cond
   ((null b) (list a))
   ((intersection a (car b))
    (eq-classes-aux (union a (car b)) (cdr b)))
   (t (cons (car b) (eq-classes-aux a (cdr b))))))

この同値類を求める手続きは間違い易い手続きです．たとえば，Winston and Horn の Lisp テキスト第一版(First Version, MIT Press 1981)のP.328の COALESCEはここで説明しているeq-classesと同じ働きをする関数です．その定義は，


(defun coalesce (classes)
  (prog
   ()
   (cond ((null classes) (return nil)))
   loop
   (cond
    ((overlap (car classes)
              (cdr classes))
     (setq classes (combine (car classes)
                            (cdr classes)))
     (go loop))
    (t (return (cons (car classes)
                     (coalesce (cdr classes))))))))

(defun intersectp (a b)
  (cond
   ((null a) nil)
   ((member (car a) b))
   (t (intersectp (cdr a) b))))
(defun overlap (a classes)
  (cond
   ((null classes) nil)
   ((intersectp a (car classes)))
   (t (overlap a (cdr classes)))))
(defun combine (a classes)
  (cond
   ((null classes) nil)
   ((intersectp a (car classes))
    (cons (union a (car classes))
          (cdr classes)))
   (t (cons (car classes)
            (combine a (cdr classes))))))

というようになっています．progを用いて繰り返し計算を行なう方法の例です．これは上で説明したように互いに素なデータのみをconsで作り上げるという方法を取っていますが，同じ著者の第二版では，P.349において


(defun coalesce (pairs)
  (coalesce-aux pairs nil))
(defun coalesce-aux (pairs classes)
  (cond
   ((null pairs) classes)
   (t (coalesce-aux (cdr pairs)
                    (absorb (car pairs) classes)))))
(defun absorb (pair classes)
  (cond
   ((null classes) (list pair))
   ((member (car pair) (car classes))
    (stick-in (cadr pair) classes))
   ((member (cadr pair) (car classes))
    (stick-in (car pair) classes))
   (t (cons (car classes)
            (absorb pair (cdr classes))))))
(defun stick-in (new classes)
  (cond
   ((member new (car classes)) classes)
   (t (cons (cons new (car classes))
            (cdr classes)))))

というように定義されています．しかし，これは，


> (coalesce '((a b) (c d) (a c)))
((C A B) (C D))

というようにうまく働きません．という具合に間違いが入り易い手続きです．ちなみに第三版ではこの手続きは取り上げられなくなりました．

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