কবিতা ক্লাব

একটি ডিসজয়েন্ট সেট (একটি ইউনিয়ন-ফাইন্ড স্ট্রাকচার) একগুচ্ছ মানকে এমন দলে দলে ভাগ করে রাখে যেগুলো একে অপরের সঙ্গে ওভারল্যাপ করে না, এবং দ্রুত একটি প্রশ্নের উত্তর দেয়: এই দুটি মান কি একই দলে আছে? এটি 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 করলে, তিনটিই শেষে একই দলে গিয়ে দাঁড়ায়।

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)

কোন অ্যাটমকে একটি দল তার রিপ্রেজেন্টেটিভ হিসেবে বেছে নেবে, সেটি অভ্যন্তরীণ বিবরণ। কখনও নির্ভর করবেন না যে একটি নির্দিষ্ট অ্যাটমই বেছে নেওয়া হবে; কেবল এইটুকুর উপর নির্ভর করুন যে একই দলের দুটি অ্যাটম একমত হয়।