Introduzione
Un insieme disgiunto (una struttura union-find) mantiene una raccolta di valori
suddivisi in gruppi non sovrapposti e risponde rapidamente a una domanda:
questi due valori sono nello stesso gruppo? Si trova nel vocabolario
disjoint-sets.
Costruire un insieme disgiunto
<disjoint-set> costruisce una struttura vuota. I valori, cioè gli atomi,
vengono aggiunti con add-atom uno alla volta, oppure con add-atoms a partire
da una sequenza. Ogni atomo inizia in un gruppo a sé.
<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'insieme disgiunto è mutabile: add-atom, add-atoms ed equate lo
modificano sul posto invece di restituirne uno nuovo. keep è comodo quando
vuoi riavere l'insieme disgiunto sullo stack dopo che una di queste parole lo ha
consumato.
Unire i gruppi
equate unisce i due gruppi che contengono i suoi atomi. L'unione è transitiva:
se si esegue l'operazione equate tra due atomi, poi tra uno di essi e un terzo,
tutti e tre finiscono in un unico gruppo.
equate ( atom1 atom2 disjoint-set -- )
Rappresentanti
Ogni gruppo ha un unico membro canonico, il suo rappresentante.
representative lo restituisce, e due atomi appartengono allo stesso gruppo
esattamente quando i loro rappresentanti sono uguali.
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)
Quale atomo un gruppo sceglie come rappresentante è un dettaglio interno: non
fare mai affidamento sul fatto che venga scelto un atomo particolare, ma solo sul
fatto che due atomi nello stesso gruppo abbiano lo stesso rappresentante.
Istruzioni
Il club di poesia locale sta iniziando una nuova stagione. I poeti si uniscono al club e, ogni volta che due di loro scrivono una poesia insieme, entrano a far parte dello stesso circolo di scrittura. Il club vuole tenere traccia di chi condivide un circolo con chi, e ti è stato chiesto di scrivere le parole che lo gestiscono.
Un insieme disgiunto è la scelta perfetta: ogni poeta è un atomo, e un circolo di scrittura è un gruppo.
1. Apri il club
Definisci new-club, che prende una sequenza di poeti e restituisce un nuovo insieme disgiunto con ogni poeta registrato. Ogni poeta parte in un circolo di scrittura tutto suo.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Registra una collaborazione
Definisci collaborate, che prende due poeti e un club. Unisce i circoli di scrittura dei due poeti e restituisce il club, così le collaborazioni si possono registrare una dopo l'altra.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Trova il circolo di un poeta
Definisci circle-of, che prende un poeta e un club e restituisce il rappresentante del circolo di scrittura di quel poeta. Due poeti che condividono un circolo riportano sempre lo stesso rappresentante.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Condividono un circolo?
Definisci same-circle?, che prende due poeti e un club e restituisce t quando entrambi i poeti appartengono allo stesso circolo di scrittura e f altrimenti. Confronta i rappresentanti dei poeti invece di usare un test di equivalenza integrato.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Esercizio di apprendimento
