Вступ
Дизʼюнктна множина (структура union-find) зберігає набір значень, розбитих на групи, що не перетинаються, і швидко відповідає на одне запитання: чи перебувають ці два значення в одній групі? Вона живе у словнику disjoint-sets.
Створення дизʼюнктної множини
<disjoint-set> створює порожню структуру. Значення (атоми) додають по одному за допомогою add-atom або з послідовності за допомогою add-atoms. Спочатку кожен атом перебуває у власній групі.
<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
Дизʼюнктна множина змінювана: add-atom, add-atoms і equate змінюють її на місці, а не повертають нову. keep стає в пригоді, коли треба повернути дизʼюнктну множину на стек після того, як одне з цих слів її спожило.
Обʼєднання груп
equate обʼєднує дві групи, які містять його атоми. Обʼєднання транзитивне: прирівняймо два атоми, потім один із них із третім, і всі три опиняться в одній групі.
equate ( atom1 atom2 disjoint-set -- )
Представники
Кожна група має одного канонічного члена, свого представника. representative повертає його, і два атоми належать до однієї групи тоді й лише тоді, коли їхні представники рівні.
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)
Те, який атом група обирає своїм представником, є внутрішньою деталлю: не покладаймося на вибір конкретного атома, а лише на те, що два атоми в одній групі узгоджуються.
Вказівки
Місцевий поетичний клуб відкриває новий сезон. Поети приєднуються до клубу, і коли двоє з них пишуть вірш разом, вони стають частиною одного письменницького кола. Клуб хоче знати, хто з ким ділить коло, і нас попросили написати слова, які всім цим керують.
Система неперетинних множин підходить якнайкраще: кожен поет - окремий елемент, а письменницьке коло - група.
1. Відкрити клуб
Визначте new-club, який приймає послідовність поетів і повертає нову систему неперетинних множин, де зареєстровано кожного поета. Кожен поет починає у власному письменницькому колі.
{ "Keats" "Byron" "Dickinson" } new-club
! => a disjoint set holding the three poets
2. Записати співпрацю
Визначте collaborate, який приймає двох поетів і клуб. Він обʼєднує письменницькі кола цих двох поетів і повертає клуб, тож співпрацю можна записувати одну за одною.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
! => the club, with Keats and Byron now in one circle
3. Знайти коло поета
Визначте circle-of, який приймає поета і клуб та повертає представника письменницького кола цього поета. Двоє поетів, які ділять одне коло, завжди мають того самого представника.
{ "Keats" "Byron" "Dickinson" } new-club
"Dickinson" swap circle-of
! => "Dickinson" (still in a circle of their own)
4. Чи ділять вони коло?
Визначте same-circle?, який приймає двох поетів і клуб та повертає t, коли обидва поети належать до одного письменницького кола, і f в іншому разі. Порівняйте представників поетів, а не використовуйте вбудований тест на еквівалентність.
{ "Keats" "Byron" "Dickinson" } new-club
"Keats" "Byron" rot collaborate
dup [ "Keats" "Byron" ] dip same-circle? . ! => t
[ "Keats" "Dickinson" ] dip same-circle? . ! => f
Навчальна вправа
