Einführung
Ein Disjoint-Set (eine Union-Find-Struktur) hält eine Sammlung von Werten, die in sich nicht überschneidende Gruppen aufgeteilt ist, und beantwortet schnell eine Frage: Sind diese beiden Werte in derselben Gruppe? Es gehört zum Vokabular disjoint-sets.
Ein Disjoint-Set aufbauen
<disjoint-set> erzeugt eine leere Struktur. Werte, also Atome, werden mit add-atom einzeln hinzugefügt oder mit add-atoms aus einer Sequenz. Jedes Atom startet in einer Gruppe für sich.
<disjoint-set> ( -- disjoint-set )
add-atom ( atom disjoint-set -- )
add-atoms ( seq disjoint-set -- )
USING: disjoint-sets ;
<disjoint-set>
{ 1 2 3 } over add-atoms ! 1, 2 and 3 each in their own group
Das Disjoint-Set ist veränderbar: add-atom, add-atoms und equate ändern es an Ort und Stelle, statt ein neues zurückzugeben. keep ist praktisch, wenn du das Disjoint-Set wieder auf dem Stack haben willst, nachdem eines dieser Wörter es verbraucht hat.
Gruppen zusammenführen
equate vereinigt die beiden Gruppen, die seine Atome enthalten. Das Vereinigen ist transitiv: Vereinige zwei Atome, dann eines davon mit einem dritten, und alle drei landen in einer Gruppe.
equate ( atom1 atom2 disjoint-set -- )
Repräsentanten
Jede Gruppe hat ein kanonisches Mitglied, ihren Repräsentanten. representative gibt ihn zurück, und zwei Atome gehören genau dann zur selben Gruppe, wenn ihre Repräsentanten gleich sind.
representative ( atom disjoint-set -- representative )
USING: disjoint-sets ;
<disjoint-set>
{ 1 2 3 } over add-atoms
1 2 pick equate
1 over representative . ! => 1
2 over representative . ! => 1 (same representative as 1)
3 over representative . ! => 3 (still on its own)
Welches Atom eine Gruppe als ihren Repräsentanten wählt, ist ein internes Detail. Verlass dich nie darauf, dass ein bestimmtes Atom gewählt wird, sondern nur darauf, dass sich zwei Atome in derselben Gruppe einig sind.
Anleitung
Der örtliche Lyrik-Club startet in eine neue Saison. Dichter treten dem Club bei,
und immer wenn zwei von ihnen gemeinsam ein Gedicht schreiben, gehören sie zum
selben Schreibzirkel. Der Club möchte den Überblick behalten, wer sich mit wem
einen Zirkel teilt, und du wurdest gebeten, die Wörter zu schreiben, die das
verwalten.
Ein Disjoint-Set passt hier perfekt: Jeder Dichter ist ein Atom und ein
Schreibzirkel ist eine Gruppe.
1. Eröffne den Club
Definiere new-club, das eine Sequenz von Dichtern entgegennimmt und ein neues
Disjoint-Set zurückgibt, in dem jeder Dichter registriert ist. Jeder Dichter
startet in einem eigenen Schreibzirkel.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Halte eine Zusammenarbeit fest
Definiere collaborate, das zwei Dichter und einen Club entgegennimmt. Es vereint
die Schreibzirkel der beiden Dichter und gibt den Club zurück, sodass sich
Zusammenarbeiten nacheinander erfassen lassen.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Finde den Zirkel eines Dichters
Definiere circle-of, das einen Dichter und einen Club entgegennimmt und den
Repräsentanten des Schreibzirkels dieses Dichters zurückgibt. Zwei Dichter, die
sich einen Zirkel teilen, melden immer denselben Repräsentanten.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Einen Zirkel teilen?
Definiere same-circle?, das zwei Dichter und einen Club entgegennimmt und t
zurückgibt, wenn beide Dichter zum selben Schreibzirkel gehören, und andernfalls
f. Vergleiche die Repräsentanten der Dichter, statt einen eingebauten
Äquivalenztest zu verwenden.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Lernübung
