कविता क्लब

एक डिसजॉइंट सेट (यानी यूनियन-फाइंड स्ट्रक्चर) वैल्यू के एक संग्रह को ऐसे समूहों में बाँटे रखता है जो आपस में नहीं मिलते। यह एक सवाल का जवाब जल्दी दे देता है: क्या ये दो वैल्यू एक ही समूह में हैं? यह 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 कीजिए, फिर उनमें से एक को तीसरे के साथ, और तीनों एक ही समूह में आ जाते हैं।

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)

किसी समूह का प्रतिनिधि कौन-सा एटम बनेगा, यह अंदरूनी बात है। कभी यह न मानिए कि कोई खास एटम ही चुना जाएगा। आप केवल इतना मानिए कि एक ही समूह के दो एटम का प्रतिनिधि एक ही होगा।