Introdução
Um conjunto disjunto (uma estrutura union-find) mantém uma coleção de valores particionada em grupos que não se sobrepõem, e responde rapidamente a uma pergunta: esses dois valores estão no mesmo grupo? Ele fica no vocabulário disjoint-sets.
Montando um conjunto disjunto
<disjoint-set> cria uma estrutura vazia. Os valores, ou átomos, são adicionados com add-atom, um de cada vez, ou com add-atoms, a partir de uma sequência. Cada átomo começa em um 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 o alteram no lugar em vez de retornar um novo. keep é útil quando você quer o conjunto disjunto de volta na pilha depois que uma dessas palavras o consumiu.
Unindo grupos
equate une os dois grupos que contêm seus átomos. A união é transitiva: use equate entre dois átomos, depois entre um deles e um terceiro, e os três acabam no mesmo grupo.
equate ( atom1 atom2 disjoint-set -- )
Representantes
Todo grupo tem um membro canônico, o seu representante. representative o retorna, e dois átomos pertencem ao mesmo grupo exatamente quando 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 átomo um grupo escolhe como representante é um detalhe interno. Nunca dependa de um átomo específico ser escolhido, apenas de que dois átomos no mesmo grupo estejam de acordo.
Instruções
O clube de poesia local está começando uma nova temporada. Os poetas entram no clube e, sempre que dois deles escrevem um poema juntos, eles passam a fazer parte do mesmo círculo de escrita. O clube quer acompanhar quem compartilha um círculo com quem, e pediram que você escrevesse as palavras que cuidam disso.
Um conjunto disjunto é perfeito para isso: cada poeta é um átomo e um círculo de escrita é um grupo.
1. Abra o clube
Defina new-club, que recebe uma sequência de poetas e retorna um novo conjunto disjunto com todos os poetas registrados. Cada poeta começa em um círculo de escrita só seu.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Registre uma colaboração
Defina collaborate, que recebe dois poetas e um clube. Ela une os círculos de escrita dos dois poetas e retorna o clube, para que as colaborações possam ser registradas uma após a outra.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Encontre o círculo de um poeta
Defina circle-of, que recebe um poeta e um clube e retorna o representante do círculo de escrita desse poeta. Dois poetas que compartilham um círculo sempre informam o mesmo representante.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Compartilham um círculo?
Defina same-circle?, que recebe dois poetas e um clube e retorna t quando os dois poetas pertencem ao mesmo círculo de escrita e f caso contrário. Compare os representantes dos poetas em vez de usar um teste de equivalência embutido.
{ "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
