3.4 集合の比較

Next: 4 例題：同値類の計算 Up: 3 集合の表現 Previous: 3.3 remove-duplicates

3.4 集合の比較

集合が同じかどうかは，


(defun set-equal (a b )
  (cond
   ((null a) (null b))
   ((member (car a) b)
      (set-equal (cdr a) (remove (car a) b)))
   (t nil)))

このように定義できますが、集合の要素が同じかどうかを調べるための:test関数を与える形で定義すれば、


(defun set-equal (a b &key (test #'eql))
  (cond
   ((null a) (null b))
   ((member (car a) b :test test)
    (set-equal (cdr a)
               (remove (car a) b :test test)
               :test test))
   (t nil)))

互いに部分集合であるかどうか、あるいは、排他的ORが空集合であれば等しい、ということであるので，


(defun set-equal (a b &key (test #'eql))	
   (and (subsetp a b) (subsetp b a)))

(defun set-equal (a b &key (test #'eql))
   (not (set-exclusive-or a b :test test)))

としてもよいが，等しくない場合に，set-exclusive-or で無駄なデータが作られるためにゴミを生みやすい定義になります．


> (set-equal '(a b c) '(b c))
NIL
> (set-equal '(a b) '(b a c))
NIL
> (set-equal '(a b) '(b a))
T
> (set-equal nil nil)
T
> (set-equal nil '(a))
NIL
> (set-equal '(a) nil)
NIL
> (set-equal '((a) (b)) '((b) (a)))
NIL 
> (set-equal '((a) (b)) '((b) (a)) :test #'equal)
T 
> (set-equal '(#\a #\b) '(#\B #\a))
NIL 
> (set-equal '(#\a #\b) '(#\B #\a)
                 :test #'char-equal)
T

この:testに自分自身のset-equalを与えれば、集合の集合同士が同じかどうかを調べることができるようになります。


USER(104): (set-equal '((a b) (c d)) '((d c) (b a)))
NIL
USER(105): (set-equal '((a b) (c d))
                      '((d c) (b a))
                      :test #'set-equal)
T

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