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

پیمایش زیرماسک‌ها

پیمایش تمام زیرماسک‌های یک ماسک معین

با داشتن یک بیت‌ماسک $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 استفاده کنید ...

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

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

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

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

بنابراین، این الگوریتم تمام زیرماسک‌های این ماسک را به ترتیب نزولی تولید می‌کند و در هر تکرار تنها دو عملیات انجام می‌دهد.

یک حالت خاص زمانی است که $s = 0$ باشد. پس از اجرای $s-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 و m ...

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

اثبات اول: بیت $i$-ام را در نظر بگیرید. دقیقاً سه گزینه برای آن وجود دارد:

  1. در ماسک $m$ وجود ندارد (و بنابراین در زیرماسک $s$ نیز وجود ندارد)،
  2. در $m$ وجود دارد، اما در $s$ وجود ندارد، یا
  3. هم در $m$ و هم در $s$ وجود دارد.

از آنجایی که در مجموع $n$ بیت وجود دارد، $3^n$ ترکیب مختلف خواهیم داشت.

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

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

برای محاسبه این عدد، توجه کنید که مجموع بالا با بسط $(1+2)^n$ با استفاده از قضیه دوجمله‌ای برابر است. بنابراین، همانطور که می‌خواستیم ثابت کنیم، $3^n$ ترکیب داریم.

مسائل تمرینی