پرش به محتویات

پیمایش زیرماسک‌ها (Submasks)

چطوری روی همه‌ی زیرماسک‌های یه ماسک مشخص بچرخیم؟

فرض کن یه بیت‌ماسک $m$ داریم و می‌خوایم خیلی بهینه روی تمام زیرماسک‌هاش حرکت کنیم. منظور از زیرماسک چیه؟ یعنی اون ماسک‌هایی ($s$) که فقط بیت‌هایی توشون روشنه که توی ماسک اصلی ($m$) هم روشن بودن.

بیا این پیاده‌سازی رو ببین که با چندتا ترفند باحال بیتی کار می‌کنه: 

int s = m;
while (s > 0) {
 ... اینجا می‌تونی از s استفاده کنی ...
 s = (s-1) & m;
}

یا اگه دوست داری کد جمع‌وجورتری داشته باشی، با یه حلقه‌ی for:

for (int s=m; s; s=(s-1)&m)
 ... اینجا می‌تونی از s استفاده کنی ...

توی هر دو تا کد بالا، زیرماسک صفر (0) پردازش نمیشه. می‌تونیم صفر رو جدا بیرون حلقه حساب کنیم، یا یه راه یکم کثیف‌تر هم هست که از این ساختار استفاده کنیم:

for (int s=m; ; s=(s-1)&m) {
 ... اینجا می‌تونی از s استفاده کنی ...
 if (s==0)  break;
}

حالا بیا ببینیم این کد جادویی چرا کار می‌کنه و چطوری تمام زیرماسک‌های $m$ رو بدون تکرار و به ترتیب از بزرگ به کوچیک پیدا می‌کنه.

فرض کن ماسک فعلی ما $s$ هست و می‌خوایم بریم سراغ زیرماسک بعدی. وقتی از $s$ یه دونه کم می‌کنیم (s-1)، اتفاقی که میفته اینه که راست‌ترین بیتِ روشنِ $s$ خاموش میشه و تمام بیت‌های سمت راستش روشن (۱) میشن. حالا یه سری بیتِ ۱ «اضافی» داریم که توی ماسک اصلی‌مون یعنی $m$ نبودن، پس نباید توی زیرماسک هم باشن. با عملیات & m این بیت‌های اضافی رو حذف می‌کنیم. در واقع (s-1) & m میاد ماسک s-1 رو یه جورایی «هرس» می‌کنه و بزرگترین مقداری که یه زیرماسک می‌تونه داشته باشه و از $s$ کوچیک‌تر باشه رو به ما میده.

خلاصه که این الگوریتم همه زیرماسک‌ها رو به ترتیب نزولی تولید می‌کنه و توی هر تکرار فقط دوتا عملیات ساده انجام میده.

یه نکته خیلی مهم در مورد حالت خاص $s = 0$ هست. اگه s صفر باشه، s-1 میشه -۱، که نمایش باینری‌ش همه‌ی بیت‌هاش یکه. بعد که با $m$ اَندِش (&) می‌کنیم، نتیجه خود $m$ میشه. پس باید حواست باشه، اگه حلقه‌ت روی صفر تموم نشه، ممکنه بیفتی تو یه لوپ بی‌نهایت!

پیمایش تمام ماسک‌ها به همراه زیرماسک‌هایشان. پیچیدگی $O(3^n)$

توی خیلی از مسئله‌ها، مخصوصا تو بحث برنامه‌نویسی پویا با بیت‌ماسک (Bitmask DP)، لازمه که روی همه‌ی بیت‌ماسک‌ها بچرخی و بعد به ازای هر کدوم، روی تمام زیرماسک‌هاش هم یه حلقه بزنی. یه چیزی شبیه این:

for (int m=0; m<(1<<n); ++m)
    for (int s=m; s; s=(s-1)&m)
 ... اینجا به s و m دسترسی داری ...

حالا بیا ثابت کنیم که حلقه داخلی در مجموع $O(3^n)$ بار اجرا میشه.

اثبات اول: بیا یه لحظه فقط روی بیت $i$-ام تمرکز کنیم. برای این بیت، کلاً سه تا حالت می‌تونه پیش بیاد:

  1. نه توی ماسک $m$ هست و نه توی زیرماسک $s$ (یعنی تو هر دو صفره).
  2. توی $m$ هست ولی توی $s$ نیست (یعنی توی $m$ یکه و توی $s$ صفره).
  3. هم توی $m$ هست و هم توی $s$ (یعنی تو هر دو یکه).

خب، چون $n$ تا بیت داریم و هر بیت ۳ تا انتخاب داره، در کل $3^n$ تا ترکیب مختلف خواهیم داشت.

اثبات دوم: یه جور دیگه هم میشه بهش نگاه کرد. فرض کن ماسک $m$ دقیقاً $k$ تا بیت روشن داشته باشه. خب، این ماسک چند تا زیرماسک داره؟ $2^k$ تا. حالا سوال اینه که ما کلاً چند تا ماسک داریم که $k$ تا بیت روشن دارن؟ جوابش میشه $\binom{n}{k}$ (همون ترکیب خودمون، یادت که نرفته؟ اگه آره یه نگاه به ضرایب دوجمله‌ای بنداز). پس تعداد کل حالت‌ها میشه جمع این دو تا برای تمام $k$ های ممکن:

$$\sum_{k=0}^n \binom{n}{k} \cdot 2^k$$

این فرمول آشنا نیست؟ این دقیقاً همون بسط دوجمله‌ای برای $(1+2)^n$ هست! پس جواب میشه $3^n$. به همین سادگی!

مسائل تمرینی