Introducción
Un conjunto disjunto (una estructura union-find) mantiene una colección de valores dividida en grupos que no se superponen, y responde rápidamente una pregunta: ¿estos dos valores están en el mismo grupo? Vive en el vocabulario disjoint-sets.
Cómo construir un conjunto disjunto
<disjoint-set> construye una estructura vacía. Los valores (los átomos) se agregan con add-atom uno a la vez, o con add-atoms a partir de una secuencia. Cada átomo empieza en un grupo propio.
<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
El conjunto disjunto es mutable: add-atom, add-atoms y equate lo modifican en el lugar en vez de devolver uno nuevo. keep es útil cuando quieres que el conjunto disjunto vuelva a quedar en la pila después de que una de esas palabras lo haya consumido.
Cómo unir grupos
equate une los dos grupos que contienen sus átomos. La unión es transitiva: iguala dos átomos y luego uno de ellos con un tercero, y los tres terminan en un solo grupo.
equate ( atom1 atom2 disjoint-set -- )
Representantes
Cada grupo tiene un miembro canónico, su representante. representative lo devuelve, y dos átomos pertenecen al mismo grupo exactamente cuando sus representantes son iguales.
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)
Cuál átomo elige un grupo como su representante es un detalle interno: nunca dependas de que se elija un átomo en particular, solo de que dos átomos del mismo grupo coincidan.
Instrucciones
El club de poesía local está empezando una nueva temporada. Los poetas se unen al club y, cada vez que dos de ellos coescriben un poema, pasan a formar parte del mismo círculo de escritura. El club quiere llevar un registro de quién comparte un círculo con quién, y a ti te han pedido escribir las palabras que lo administran.
Un conjunto disjunto es la opción perfecta: cada poeta es un átomo y un círculo de escritura es un grupo.
1. Abrir el club
Define new-club, que toma una secuencia de poetas y devuelve un conjunto disjunto nuevo con cada poeta registrado. Cada poeta empieza en un círculo de escritura propio.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Registrar una colaboración
Define collaborate, que toma dos poetas y un club. Fusiona los círculos de escritura de los dos poetas y devuelve el club, para que las colaboraciones se puedan registrar una tras otra.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Encontrar el círculo de un poeta
Define circle-of, que toma un poeta y un club y devuelve el representante del círculo de escritura de ese poeta. Dos poetas que comparten un círculo siempre reportan el mismo representante.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. ¿Comparten un círculo?
Define same-circle?, que toma dos poetas y un club y devuelve t cuando ambos poetas pertenecen al mismo círculo de escritura y f en caso contrario. Compara los representantes de los poetas en lugar de usar una prueba de equivalencia incorporada.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Ejercicio de aprendizaje
