Introducción
Un conjunto disjunto (una estructura union-find) mantiene una colección de valores repartidos en grupos que no se solapan y responde con rapidez a una pregunta: ¿estos dos valores están en el mismo grupo? Vive en el vocabulario disjoint-sets.
Construir un conjunto disjunto
<disjoint-set> construye una estructura vacía. Los valores, los átomos, se añaden con add-atom de uno en uno, o con add-atoms a partir de una secuencia. Cada átomo empieza en un grupo por sí solo.
<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 sitio en lugar de devolver uno nuevo. keep resulta práctico cuando quieres recuperar el conjunto disjunto en la pila después de que una de estas palabras se lo haya llevado.
Fusionar grupos
equate une los dos grupos que contienen sus átomos. La unión es transitiva: une dos átomos y después uno de ellos con un tercero, y los tres acaban en un mismo 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)
Qué átomo elige un grupo como representante es un detalle interno; no dependas nunca de que se elija un átomo concreto, solo de que dos átomos del mismo grupo coincidan.
Instrucciones
El club de poesía local empieza una nueva temporada. Los poetas se unen al club y, cuando dos de ellos escriben un poema juntos, 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 te han pedido que escribas las palabras que lo gestionan.
Un conjunto disjunto es la opción perfecta: cada poeta es un átomo y un círculo de escritura es un grupo.
1. Abre el club
Define new-club, que toma una secuencia de poetas y devuelve un conjunto disjunto nuevo con todos los poetas registrados. Cada poeta empieza en un círculo de escritura propio.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Registra 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. Encuentra 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 devuelven 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
