Bevezetés
A diszjunkt halmaz (egy union-find adatszerkezet) értékek egy gyűjteményét
tartja egymást nem átfedő csoportokra osztva, és gyorsan válaszol egy
kérdésre: ugyanabban a csoportban van ez a két érték? A
disjoint-sets szókészletben található.
Diszjunkt halmaz felépítése
A <disjoint-set> egy üres szerkezetet hoz létre. Az értékeket, az
atomokat, vagy egyesével adod hozzá az add-atom szóval, vagy egy
sorozatból az add-atoms szóval. Minden atom egyedül, a saját csoportjában
indul.
<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
A diszjunkt halmaz módosítható: az add-atom, az add-atoms és az
equate helyben módosítja, ahelyett hogy egy újat adna vissza. A keep
akkor hasznos, ha vissza szeretnéd kapni a diszjunkt halmazt a veremre,
miután valamelyik ilyen szó elfogyasztotta.
Csoportok egyesítése
Az equate egyesíti azt a két csoportot, amelyben a két atomja
található. Az egyesítés tranzitív: egyesíts két atomot, majd az egyiket egy
harmadikkal, és mindhárom ugyanabba a csoportba kerül.
equate ( atom1 atom2 disjoint-set -- )
Reprezentánsok
Minden csoportnak egyetlen kanonikus tagja van, a reprezentánsa.
A representative ezt adja vissza, és két atom pontosan akkor tartozik
ugyanahhoz a csoporthoz, ha a reprezentánsaik megegyeznek.
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)
Az, hogy egy csoport melyik atomot választja reprezentánsnak, belső
részlet. Soha ne arra számíts, hogy egy adott atomot választ, hanem csak
arra, hogy két, ugyanabba a csoportba tartozó atom reprezentánsa
megegyezik.
Utasítások
A helyi költőklub új évadot kezd. A költők csatlakoznak a klubhoz, és valahányszor ketten közösen írnak egy verset, ugyanannak az írókörnek a tagjaivá válnak. A klub szeretné nyomon követni, hogy ki kivel osztozik egy írókörön, és téged kértek meg, hogy megírd azokat a szavakat, amelyek ezt kezelik.
A diszjunkt halmaz pont ideális erre: minden költő egy atom, és egy írókör egy csoport.
1. Nyisd meg a klubot
Definiáld a new-club szót, amely egy költők sorozatát veszi át, és egy friss diszjunkt halmazt ad vissza, amelyben minden költő regisztrálva van. Minden költő a saját írókörében kezd.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Jegyezz fel egy együttműködést
Definiáld a collaborate szót, amely két költőt és egy klubot vesz át. Összevonja a két költő írókörét, és visszaadja a klubot, hogy az együttműködéseket egymás után fel lehessen jegyezni.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Keresd meg egy költő írókörét
Definiáld a circle-of szót, amely egy költőt és egy klubot vesz át, és visszaadja a költő írókörének reprezentánsát. Két költő, aki ugyanabban az írókörben van, mindig ugyanazt a reprezentánst jelenti.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Közös írókörben vannak?
Definiáld a same-circle? szót, amely két költőt és egy klubot vesz át, és t-t ad vissza, ha mindkét költő ugyanahhoz az írókörhöz tartozik, egyébként pedig f-et. A költők reprezentánsait hasonlítsd össze ahelyett, hogy beépített egyenlőségvizsgálatot használnál.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Tanulófeladat
