Перебір підмасок

Перебір усіх підмасок заданої маски

Маємо бітову маску $m$ і хочемо ефективно перебрати всі її підмаски, тобто маски $s$, у яких встановлені лише ті біти, що входять до маски $m$.

Коли підходить цей алгоритм?

• Чи задача зводиться до перебору підмножин фіксованої множини бітів (динамічне програмування на масках, розбиття на групи)?
• Чи кількість елементів у масці мала ($n \lesssim 20$), щоб сумарні $O(3^n)$ ітерацій по всіх масках з їхніми підмасками вкладалися в ліміт часу? (якщо ні → Перебір підмасок надто дорогий — шукайте поліноміальний підхід, напр. бінарні коефіцієнти)
• Чи потрібно перебрати саме підмаски заданої маски, а не всі $2^n$ масок поспіль?

Розгляньмо реалізацію цього алгоритму, що ґрунтується на трюках із бітовими операціями:

C++

int s = m;
while (s > 0) {
 ... тут можна використати s ...
 s = (s-1) & m;
}

Python

s = m
while s > 0:
    # ... тут можна використати s ...
    s = (s - 1) & m

TypeScript

// Бітові оператори в JS працюють із 32-бітними цілими, тож m < 2^31
let s = m;
while (s > 0) {
  // ... тут можна використати s ...
  s = (s - 1) & m;
}

Go

s := m
for s > 0 {
    // ... тут можна використати s ...
    s = (s - 1) & m
}

або, використовуючи компактніший запис через for:

C++

for (int s=m; s; s=(s-1)&m)
 ... тут можна використати s ...

Python

# У Python немає компактного for із кроком (s-1)&m, тож лишаємо while
s = m
while s:
    # ... тут можна використати s ...
    s = (s - 1) & m

TypeScript

// Бітові оператори в JS 32-бітні, тож m < 2^31
for (let s = m; s; s = (s - 1) & m) {
  // ... тут можна використати s ...
}

Go

for s := m; s != 0; s = (s - 1) & m {
    // ... тут можна використати s ...
}

В обох варіантах коду підмаска, що дорівнює нулю, не буде оброблена. Ми можемо або обробити її поза циклом, або скористатися менш елегантною конструкцією, наприклад:

C++

for (int s=m; ; s=(s-1)&m) {
 ... тут можна використати s ...
 if (s==0)  break;
}

Python

# do-while у Python імітуємо через while True з умовою виходу всередині
s = m
while True:
    # ... тут можна використати s ...
    if s == 0:
        break
    s = (s - 1) & m

TypeScript

// Бітові оператори в JS 32-бітні, тож m < 2^31
for (let s = m; ; s = (s - 1) & m) {
  // ... тут можна використати s ...
  if (s === 0) break;
}

Go

for s := m; ; s = (s - 1) & m {
    // ... тут можна використати s ...
    if s == 0 {
        break
    }
}

Розгляньмо, чому наведений вище код відвідує всі підмаски $m$ без повторень і в спадному порядку.

Припустимо, що в нас є поточна бітова маска $s$, і ми хочемо перейти до наступної бітової маски. Віднявши від маски $s$ одиницю, ми приберемо найправіший встановлений біт, а всі біти праворуч від нього стануть рівними 1. Потім ми прибираємо всі «зайві» одиничні біти, що не входять до маски $m$ і тому не можуть бути частиною підмаски. Це прибирання ми виконуємо за допомогою побітової операції (s-1) & m. У результаті ми «обрізаємо» маску $s-1$, щоб визначити найбільше значення, якого вона може набути, тобто наступну підмаску після $s$ у спадному порядку.

Отже, цей алгоритм генерує всі підмаски даної маски у спадному порядку, виконуючи лише дві операції за ітерацію.

Окремий випадок — це коли $s = 0$. Після виконання $s-1$ ми отримаємо маску, у якій встановлені всі біти (бітове представлення -1), а після (s-1) & m матимемо, що $s$ дорівнюватиме $m$. Тому з маскою $s = 0$ слід бути обережними — якщо цикл не завершується на нулі, алгоритм може потрапити в нескінченний цикл.

Перебір усіх масок разом з їхніми підмасками. Складність $O(3^n)$

У багатьох задачах, особливо в тих, що використовують динамічне програмування на бітових масках, потрібно перебрати всі бітові маски і для кожної маски перебрати всі її підмаски:

C++

for (int m=0; m<(1<<n); ++m)
	for (int s=m; s; s=(s-1)&m)
 ... s та m ...

Python

for m in range(1 << n):
    s = m
    while s:
        # ... s та m ...
        s = (s - 1) & m

TypeScript

// Бітові оператори в JS 32-бітні, тож n < 31
for (let m = 0; m < (1 << n); ++m) {
  for (let s = m; s; s = (s - 1) & m) {
    // ... s та m ...
  }
}

Go

for m := 0; m < (1 << n); m++ {
    for s := m; s != 0; 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$ комбінацій, що й треба було довести.

Задачі для практики

• Atcoder - Close Group
• Codeforces - Nuclear Fusion
• Codeforces - Sandy and Nuts
• Uva 1439 - Exclusive Access 2
• UVa 11825 - Hackers' Crackdown