সাবমাস্ক ইনিউমারেশন#
একটা দেওয়া মাস্কের সকল সাবমাস্ক ইনিউমারেট করা#
একটি বিটমাস্ক $m$ দেওয়া আছে, তুমি দক্ষতার সাথে এর সকল সাবমাস্কের মধ্য দিয়ে ইটারেট করতে চাও, অর্থাৎ এমন মাস্ক $s$ যেখানে শুধুমাত্র সেই বিটগুলো সেট আছে যেগুলো মাস্ক $m$-এ অন্তর্ভুক্ত ছিল।
বিট অপারেশনের কৌশলের উপর ভিত্তি করে এই অ্যালগরিদমের ইমপ্লিমেন্টেশনটা দেখো:
int s = m;
while (s > 0) {
... you can use s ...
s = (s-1) & m;
}অথবা, আরও সংক্ষিপ্ত for স্টেটমেন্ট ব্যবহার করে:
for (int s=m; s; s=(s-1)&m)
... you can use s ...কোডের উভয় ভেরিয়েন্টেই, শূন্যের সমান সাবমাস্কটা প্রসেস হবে না। আমরা হয় এটাকে লুপের বাইরে প্রসেস করতে পারি, অথবা একটু কম মার্জিত ডিজাইন ব্যবহার করতে পারি, যেমন:
for (int s=m; ; s=(s-1)&m) {
... you can use s ...
if (s==0) break;
}চলো পরীক্ষা করি কেন উপরের কোড $m$-এর সকল সাবমাস্ক রিপিটেশন ছাড়াই এবং অবরোহী ক্রমে ভিজিট করে।
ধরো আমাদের কাছে একটি বর্তমান বিটমাস্ক $s$ আছে, এবং আমরা পরবর্তী বিটমাস্কে যেতে চাই। মাস্ক $s$ থেকে এক বিয়োগ করলে, সবচেয়ে ডানদিকের সেট বিটটা সরিয়ে ফেলা হবে এবং এর ডানদিকের সকল বিট ১ হয়ে যাবে। তারপর আমরা সেই সব “অতিরিক্ত” ওয়ান বিট সরিয়ে ফেলি যেগুলো মাস্ক $m$-এ অন্তর্ভুক্ত নয় এবং তাই একটি সাবমাস্কের অংশ হতে পারে না। আমরা এই অপসারণটা বিটওয়াইজ অপারেশন (s-1) & m ব্যবহার করে করি। তারমানে, আমরা মাস্ক $s-1$ কে “কেটে” ফেলি যাতে এটা সর্বোচ্চ যে মান নিতে পারে তা ডিটারমিন করা যায়, অর্থাৎ অবরোহী ক্রমে $s$-এর পরের সাবমাস্ক।
এইভাবে, এই অ্যালগরিদম অবরোহী ক্রমে এই মাস্কের সকল সাবমাস্ক তৈরি করে, প্রতি ইটারেশনে মাত্র দুটি অপারেশন করে।
একটি বিশেষ ক্ষেত্র হলো যখন $s = 0$। $s-1$ এক্সিকিউট করার পর আমরা একটি মাস্ক পাই যেখানে সকল বিট সেট (-1-এর বিট রিপ্রেজেন্টেশন), এবং (s-1) & m-এর পর $s$-এর মান $m$-এর সমান হবে। তাই মাস্ক $s = 0$-এর ক্ষেত্রে সতর্ক থেকো — যদি লুপ শূন্যে শেষ না হয়, তাহলে অ্যালগরিদম একটি অসীম লুপে (infinite loop) ঢুকতে পারে।
সকল মাস্কের সাথে তাদের সাবমাস্কগুলোর মধ্য দিয়ে ইটারেশন। কমপ্লেক্সিটি $O(3^n)$#
অনেক সমস্যায়, বিশেষ করে যেগুলো বিটমাস্ক ডায়নামিক প্রোগ্রামিং (DP) ব্যবহার করে, তুমি সকল বিটমাস্কের মধ্য দিয়ে ইটারেট করতে চাও এবং প্রতিটি মাস্কের জন্য, এর সকল সাবমাস্কের মধ্য দিয়ে ইটারেট করতে চাও:
for (int m=0; m<(1<<n); ++m)
for (int s=m; s; s=(s-1)&m)
... s and m ...চলো প্রুফ করি যে ভেতরের লুপটা মোট $O(3^n)$ বার ইটারেশন করবে।
প্রথম প্রুফ: $i$-তম বিট কনসিডার করো। এর জন্য ঠিক তিনটি সম্ভাবনা আছে:
১. এটা মাস্ক $m$-এ অন্তর্ভুক্ত নয় (এবং তাই সাবমাস্ক $s$-এও অন্তর্ভুক্ত নয়), ২. এটা $m$-এ অন্তর্ভুক্ত, কিন্তু $s$-এ অন্তর্ভুক্ত নয়, অথবা ৩. এটা $m$ এবং $s$ উভয়তেই অন্তর্ভুক্ত।
মোট $n$ টি বিট থাকায়, $3^n$ টি ভিন্ন কম্বিনেশন হবে।
দ্বিতীয় প্রুফ: লক্ষ্য করো যে মাস্ক $m$-এ $k$ টি সক্রিয় বিট থাকলে, এর $2^k$ টি সাবমাস্ক থাকবে। যেহেতু $k$ টি সক্রিয় বিটসহ মোট $\binom{n}{k}$ টি মাস্ক আছে (বাইনোমিয়াল কোএফিশিয়েন্ট দেখো), তাহলে সকল মাস্কের জন্য মোট কম্বিনেশন সংখ্যা হবে:
$$\sum_{k=0}^n \binom{n}{k} \cdot 2^k$$এই সংখ্যা গণনা করতে, লক্ষ্য করো যে উপরের যোগফলটা বাইনোমিয়াল থিওরেম ব্যবহার করে $(1+2)^n$-এর বিস্তৃতির সমান। তাই, আমরা যেমন প্রুফ করতে চেয়েছিলাম, $3^n$ টি কম্বিনেশন পাই।