A1(let ((p (new partition))) (progn (make-set p (list 1)) (make-set p (list 2)) (make-set p (list 3)) (join-sets p 1 2) p))B1(get-set-count @a!1!)B2(in-same-set? @a!1! 1 2)B3(in-same-set? @a!1! 1 3)(defmacro alter-by args (quasi-quote (.= (unquote (first args)) (unquote (second args)) (+ (unquote (third args)) (. (unquote (first args)) (unquote (second args))))))) #| partition of a set |# (defclass set ()) (defmethod initialize ((this set)) t (progn (.= this rank 0) this)) (defmethod find-root ((this set)) t (aif (. this parent) (.= this parent (find-root it)) this)) (defmethod has-smaller-rank? ((this set) (that set)) t (< (. this rank) (. that rank))) (defclass partition ()) (defmethod initialize ((this partition)) t (progn (.= this map (make-hash-table)) (.= this part-count 0) this)) (defmethod make-set ((this partition) elements) (every? (lambda (element) (null? (get-hash-table-value (. this map) element))) elements) (let ((that (new set))) (progn (alter-by this part-count 1) (dolist (element elements that) (put-hash-table-value (. this map) element that))))) (defmethod find-set ((this partition) element) t (find-root (get-hash-table-value (. this map) element))) (defmethod in-same-set? ((this partition) element-1 element-2) t (= (find-set this element-1) (find-set this element-2))) (defmethod join-sets ((this partition) element-1 element-2) t (let ((set-1 (find-set this element-1)) (set-2 (find-set this element-2))) (unless (= set-1 set-2) (alter-by this part-count -1) (cond ((has-smaller-rank? set-1 set-2) (.= set-1 parent set-2)) ((has-smaller-rank? set-2 set-1) (.= set-2 parent set-1)) (t (progn (.= set-2 parent set-1) (alter-by set-1 rank 1))))))) (defmethod get-set-count ((this partition)) t (. this part-count))union-findBei einer Partition (repräsentiert durch Instanzen der Klasse partition) handelt es sich um die Aufteilung einer Menge in disjunkte Teilmengen (repräsentiert durch Instanzen der Klasse set). Die Methode make-set legt innerhalb der Partition eine neue Teilmenge mit den übergebenen Elementen an. Die angegebenen Elemente dürfen nicht in einer anderen Teilmenge enthalten sein. Die Methode find-set liefert zu einem Element die Teilmenge der Partition, in der es enthalten ist. Davon abgeleitet prüft die Methode in-same-set?, ob zwei Elemente zur selben Teilmenge gehören. Die Methode join-sets verschmilzt zwei Teilmengen der Partition. Die Teilmengen werden durch zwei Elemente identifiziert. Die Methode get-set-count zählt, aus wie vielen Teilmengen die Partition besteht.set partition initialize make-set find-set in-same-set? join-sets get-set-count1101000101001101101100110001110010110100000010101111101110001111