Bei einer Partition handelt es sich um die Aufteilung einer Menge in disjunkte Teilmengen.

Eine effiziente Datenstruktur, die eine Partition einer Menge repräsentieren kann und die Operationen

- finde heraus, in welcher Teilmenge sich ein Element befindet
- prüfe, ob zwei Elemente in der selben Teilmenge sind und
- verschmelze zwei Teilmengen zu einer

unterstützt, wird z.B. für den Algorithmus von Kruskal zum Finden von Spannbäumen benötigt (siehe minimale aufspannende Bäume).

Aus Gründen der Bequemlichkeit wird ein Macro definiert:

(defmacro alter-by args
  (quasi-quote
    (.=
      (unquote (first args))
      (unquote (second args))
      (+ (unquote (third args))
        (.
          (unquote (first args))
          (unquote (second args)))))))

Das Macro alter-by verändert den Wert einer Instanzvariablen. Die Instanz wird als erstes Argument erwartet, der Name der Instanzvariablen als zweites Argument und der Wert, der addiert werden soll, als drittes und letztes Argument.

Die Instanzen der Klasse set stellen die Teilmengen dar.

(defclass set ())

(defmethod initialize ((this set))
  t
  (progn
    (.= this rank 0)
    this))

Damit Teilmengen effizent verschmolzen werden können, bilden diese mehrere Bäume. Die Instanzvariable parent einer Teilmenge verweist auf eine andere Teilmenge, nachdem die beiden verschmolzen wurden. Die Methode find-root verfolgt die Verweise bis zur Wurzel. Dabei werden die Verweise abgekürzt, d.h. so korrigiert, dass Zwischenstationen übersprungen werden.

(defmethod find-root ((this set))
  t
  (aif
    (. this parent)
    (.= this parent (find-root it))
    this))

Der Rang einer Menge gibt an, wieviele übergeordnete Mengen sie hat. Die Methode has-smaller-rank? vergleicht die Ränge zweier Mengen.

(defmethod has-smaller-rank? ((this set) (that set))
  t
  (< (. this rank) (. that rank)))

Die Instanzen der Klasse partition repräsentieren Partitionen.

(defclass partition ())

(defmethod initialize ((this partition))
  t
  (progn
    (.= this map (make-hash-table))
    (.= this part-count 0)
    this))

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.

(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)))))

Die Methode find-set liefert zu einem Element die Teilmenge der Partition, in der es enthalten ist.

(defmethod find-set ((this partition) element)
  t
  (find-root (get-hash-table-value (. this map) element)))

Davon abgeleitet prüft die Methode in-same-set?, ob zwei Elemente zur selben Teilmenge gehören.

(defmethod in-same-set? ((this partition) element-1 element-2)
  t
  (=
    (find-set this element-1)
    (find-set this element-2)))

Die Methode join-sets verschmilzt zwei Teilmengen der Partition. Die Teilmengen werden durch zwei Elemente identifiziert.

(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)))))))

Schließlich zählt die Methode get-set-count, aus wie vielen Teilmengen die Partition besteht.

(defmethod get-set-count ((this partition))
  t
  (. this part-count))

Link
https://en.wikipedia.org/wiki/Disjoint-set_data_structure