Introduction
Un ensemble disjoint (une structure union-find) conserve une collection de valeurs réparties en groupes qui ne se recouvrent pas, et répond rapidement à une question : ces deux valeurs sont-elles dans le même groupe ? On le trouve dans le vocabulaire disjoint-sets.
Construis un ensemble disjoint
<disjoint-set> construit une structure vide. On ajoute les valeurs, les atomes, un par un avec add-atom, ou à partir d'une séquence avec add-atoms. Chaque atome démarre dans un groupe qui lui est propre.
<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
L'ensemble disjoint est mutable : add-atom, add-atoms et equate le modifient sur place au lieu de renvoyer un nouvel ensemble. keep est pratique quand tu veux récupérer l'ensemble disjoint sur la pile après que l'un de ces mots l'a consommé.
Fusionne les groupes
equate réunit les deux groupes qui contiennent ses atomes. L'union est transitive : si tu associes deux atomes, puis l'un d'eux avec un troisième, les trois se retrouvent dans un seul groupe.
equate ( atom1 atom2 disjoint-set -- )
Représentants
Chaque groupe a un membre canonique, son représentant. representative le renvoie, et deux atomes appartiennent au même groupe précisément quand leurs représentants sont égaux.
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)
L'atome qu'un groupe choisit comme représentant est un détail interne : ne te fie jamais à ce qu'un atome précis soit choisi, seulement au fait que deux atomes du même groupe s'accordent.
Instructions
Le club de poésie du quartier entame une nouvelle saison. Les poètes rejoignent le club et, chaque fois que deux d'entre eux coécrivent un poème, ils font partie du même cercle d'écriture. Le club veut garder la trace de qui partage un cercle avec qui, et on t'a demandé d'écrire les mots qui s'en chargent.
Un ensemble disjoint est le choix idéal : chaque poète est un atome, et un cercle d'écriture est un groupe.
1. Ouvre le club
Définis new-club, qui prend une séquence de poètes et renvoie un nouvel ensemble disjoint où chaque poète est enregistré. Chaque poète commence dans son propre cercle d'écriture.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Enregistre une collaboration
Définis collaborate, qui prend deux poètes et un club. Il fusionne les cercles d'écriture des deux poètes et renvoie le club, ce qui permet d'enregistrer les collaborations les unes après les autres.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Trouve le cercle d'un poète
Définis circle-of, qui prend un poète et un club et renvoie le représentant du cercle d'écriture de ce poète. Deux poètes qui partagent un cercle donnent toujours le même représentant.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Partage un cercle ?
Définis same-circle?, qui prend deux poètes et un club et renvoie t quand les deux poètes appartiennent au même cercle d'écriture et f sinon. Compare les représentants des poètes plutôt que d'utiliser un test d'équivalence intégré.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Exercice d'apprentissage
