Introdução
Um conjunto disjunto (uma estrutura união-busca) mantém uma coleção de valores repartida por grupos que não se sobrepõem, e responde rapidamente a uma pergunta: estes dois valores estão no mesmo grupo? Vive no vocabulário disjoint-sets.
Construir um conjunto disjunto
<disjoint-set> cria uma estrutura vazia. Os valores (os átomos) são adicionados com add-atom, um a um, ou com add-atoms, a partir de uma sequência. Cada átomo começa num grupo só para si.
<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
O conjunto disjunto é mutável: add-atom, add-atoms e equate alteram-no no local em vez de devolverem um novo. O keep dá jeito quando queres o conjunto disjunto de volta na pilha depois de uma destas palavras o ter consumido.
Unir grupos
O equate une os dois grupos que contêm os seus átomos. A união é transitiva: usa equate em dois átomos, depois num deles e num terceiro, e os três acabam num único grupo.
equate ( atom1 atom2 disjoint-set -- )
Representantes
Cada grupo tem um membro canónico, o seu representante. O representative devolve-o, e dois átomos pertencem ao mesmo grupo exatamente quando os seus representantes são iguais.
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)
Qual o átomo que um grupo escolhe como representante é um detalhe interno. Nunca dependas de que seja escolhido um átomo em particular, mas apenas de que dois átomos do mesmo grupo estejam de acordo.
Instruções
O clube de poesia local está a começar uma nova temporada. Os poetas juntam-se ao clube e, sempre que dois deles escrevem um poema a quatro mãos, passam a fazer parte do mesmo círculo de escrita. O clube quer manter registo de quem partilha um círculo com quem, e pediram-te que escrevas as palavras que fazem essa gestão.
Um conjunto disjunto é a escolha perfeita: cada poeta é um átomo e cada círculo de escrita é um grupo.
1. Abre o clube
Define new-club, que recebe uma sequência de poetas e devolve um conjunto disjunto novo com todos os poetas registados. Cada poeta começa num círculo de escrita só seu.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Regista uma colaboração
Define collaborate, que recebe dois poetas e um clube. Une os círculos de escrita dos dois poetas e devolve o clube, para que as colaborações possam ser registadas uma a seguir à outra.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Encontra o círculo de um poeta
Define circle-of, que recebe um poeta e um clube e devolve o representante do círculo de escrita desse poeta. Dois poetas que partilham um círculo indicam sempre o mesmo representante.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Partilham um círculo?
Define same-circle?, que recebe dois poetas e um clube e devolve t quando ambos os poetas pertencem ao mesmo círculo de escrita e f caso contrário. Compara os representantes dos poetas em vez de usar um teste de equivalência incorporado.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Exercício de aprendizagem
