সাবমাস্ক ইনিউমারেশন#
একটি প্রদত্ত মাস্কের সকল সাবমাস্ক ইনিউমারেট করা#
একটি বিটমাস্ক $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$-এর ক্ষেত্রে সতর্ক থাকুন — যদি লুপ শূন্যে শেষ না হয়, তাহলে অ্যালগরিদম একটি অসীম লুপে প্রবেশ করতে পারে।
সকল মাস্কের সাথে তাদের সাবমাস্কগুলোর মধ্য দিয়ে ইটারেশন। কমপ্লেক্সিটি $O(3^n)$#
অনেক সমস্যায়, বিশেষ করে যেগুলো বিটমাস্ক ডায়নামিক প্রোগ্রামিং ব্যবহার করে, আপনি সকল বিটমাস্কের মধ্য দিয়ে ইটারেট করতে চান এবং প্রতিটি মাস্কের জন্য, এর সকল সাবমাস্কের মধ্য দিয়ে ইটারেট করতে চান:
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$ টি কম্বিনেশন পাই।