Перебор подмасок: все подмножества всех множеств за 3ⁿ

Если ты напишешь цикл по подмаскам, объяснишь, почему (s - 1) & m не пропускает ни одной, и выведешь, откуда берётся 3ⁿ, - листай до «Теперь сам».

Как думаешь, сколько пар «множество и его часть»

Элементов десять. Нужно перебрать все пары (m, s), где m - какое-то множество этих элементов, а s - какая-то его часть. Множеств 1024, частей у каждого - не больше 1024.

Прежде чем читать дальше, оцени число пар: около миллиона или заметно меньше? Ответ - 59 049, это 3¹⁰. Миллион получится, если для каждого m проверять все 1024 кандидата и выбрасывать неподходящие; почти все проверки при этом уходят в мусор.

На что это похоже

Счётчик из четырёх колёсиков, на каждом ноль или единица, и он считает назад: 1111, 1110, 1101 и так далее. Теперь одно колёсико заклеено на нуле, скажем второе справа. Счётчик по-прежнему считает назад, но заклеенное колёсико стоит: 1101, 1100, 1001, 1000, 0101. Он проходит все положения свободных колёсиков и ни одного лишнего.

Заклеенные колёсики - биты, которых нет в множестве. Свободные - биты множества. Осталось заставить обычное вычитание перепрыгивать заклеенные разряды.

Механизм: шаг назад и возврат в рамки

Подмаска маски m - число s, у которого единицы стоят только там, где они есть у m: s & m == s. Это запись подмножества.

Что делает вычитание единицы с двоичным числом: самая правая единица становится нулём, а все нули правее неё - единицами. Остальное не меняется.

s      = 1 0 1 1 0 0 0
s - 1  = 1 0 1 0 1 1 1
               ↑ была младшая единица

Отсюда сразу полезное: s & (s - 1) - это s без младшей единицы, потому что всё левее неё совпало, в её разряде у s − 1 стоит ноль, а ниже нули у самого s.

Пусть s - подмаска m. В s - 1 появились единицы на местах ниже погашенной, и часть из них стоит на заклеенных разрядах. & m их стирает, а единицы на разрешённых местах оставляет все. Получается подмаска, в которой ниже погашенного бита включено всё, что можно, - то есть самая большая подмаска, меньшая s. Это и есть обратный счёт по свободным колёсикам.

m = 1101
s           s - 1        (s - 1) & m
1101        1100         1100
1100        1011         1001        единица встала на заклеенный разряд и стёрта
1001        1000         1000
1000        0111         0101
0101        0100         0100
0100        0011         0001
0001        0000         0000

Восемь подмасок у множества из трёх элементов, каждая ровно по разу, по убыванию.

Откуда 3ⁿ. У каждого из n элементов в паре (m, s) три возможных состояния: его нет в m; он есть в m, но не в s; он есть и там и там. Четвёртое - «есть в s, но нет в m» - запрещено. Состояния элементов независимы, пар 3 · 3 · … · 3 = 3ⁿ.

Правило

Подмаски m по убыванию: s = m, затем s = (s - 1) & m, пока s больше нуля; пустую подмаску обрабатывают отдельно. Проходов - 2ᵏ, где k - число единиц в m. Перебор подмасок у всех масок из n битов - 3ⁿ проходов. s & (s - 1) убирает из s младшую единицу.

Разбор: список подмасок и счёт пар

def podmaski(m):
    spisok = []
    s = m
    while s > 0:
        spisok.append(s)
        s = (s - 1) & m
    spisok.append(0)
    return spisok

p = podmaski(0b1101)
print(len(p), p)

8 [13, 12, 9, 8, 5, 4, 1, 0]

Теперь счёт пар двумя способами. Первый - для каждой маски m от 0 до 2ⁿ − 1 запустить цикл по её подмаскам и считать круги. Второй - для каждой маски проверить все числа от 0 до 2ⁿ − 1 условием s & m == s.

n     пар      шагов: подмаски     шагов: проверка всех
4       81            261                    611
6      729          2 253                  8 987
8    6 561         19 941                137 891

Число пар совпало с 3⁴, 3⁶ и 3⁸. Первый способ тратит около трёх шагов на пару. Второй растёт как 4ⁿ: при n = 8 он в семь раз дороже, при n = 16 разница была бы уже в десятки раз.

Разбор: грузы по машинам, и где 3ⁿ перестаёт помещаться

Есть n грузов с весами и машины грузоподъёмностью W. Нужно наименьшее число машин, чтобы увезти всё. Жадно грузить по порядку нельзя: ответ зависит от того, какие грузы поедут вместе.

Пусть mashin[m] - наименьшее число машин для множества грузов m. Последняя машина увозит какую-то часть s этого множества, лишь бы её вес был не больше W, а остаток m ^ s развозится наилучшим способом, который уже посчитан: остаток - число, меньшее m. Веса лежат в списке ves, грузоподъёмность - в W; значения для двух прогонов - в таблице под программой.

n = len(ves)
vsego = 1 << n
summa = [0] * vsego
for m in range(1, vsego):
    mladshij = 0
    while m >> mladshij & 1 == 0:
        mladshij = mladshij + 1
    summa[m] = summa[m & (m - 1)] + ves[mladshij]

mashin = [n + 1] * vsego
mashin[0] = 0
proverok = 0
for m in range(1, vsego):
    s = m
    while s > 0:
        proverok = proverok + 1
        if summa[s] <= W and mashin[m ^ s] + 1 < mashin[m]:
            mashin[m] = mashin[m ^ s] + 1
        s = (s - 1) & m
print(mashin[vsego - 1], proverok)

Первый цикл считает вес каждого множества: вес m - это вес m без младшего элемента плюс этот элемент. Второй перебирает подмаски. m ^ s здесь - разность: s лежит внутри m, и ^ просто гасит её биты. Начальное значение n + 1 заведомо больше любого ответа: машин не нужно больше, чем грузов.

веса                         W     машин    проверок    шагов
4, 8, 1, 4, 2, 1            10       2         665       3 416
6, 5, 5, 4, 4, 3, 2, 1      10       3       6 305      28 306

Проверок 3ⁿ − 2ⁿ: 729 − 64 и 6561 − 256. Вычитается 2ⁿ, потому что цикл не заходит в пустую подмаску - машина без груза ответ не улучшает.

Граница - сама тройка в степени. 3¹⁵ - это 14 миллионов, 3²⁰ - три с половиной миллиарда. Перебор подмасок работает до 15-18 элементов; таблица на 2ⁿ ячеек при этом ещё мала. Если нужна не лучшая часть, а сумма по всем частям каждого множества, есть способ дешевле, за n · 2ⁿ: таблицу пересчитывают n раз, каждый раз разрешая отличаться ещё одному элементу.

Что ломается без этого

Первое: условие s >= 0. Из нуля шаг даёт (0 - 1) & m. Минус единица - все единицы, и & m возвращает m: счётчик прокрутился на начало, цикл бесконечен. Пустую подмаску обрабатывают после цикла или выходят по break, когда s == 0.

Второе: забытый & m. Без него s просто убывает через все числа, включая те, что не подмаски. Ответ может остаться верным, если ниже стоит проверка, но перебор снова стоит 4ⁿ.

Третье: порядок заполнения. Таблица читает mashin[m ^ s]. Это законно, только если маски идут по возрастанию: любая часть множества как число меньше самого множества. При обходе в другом порядке читается ещё не посчитанная ячейка.

Четвёртое: одно разбиение считается много раз. Разложение на три машины цикл найдёт шестью способами - в любом порядке машин. Для минимума это лишняя работа, для подсчёта числа разбиений - неверный ответ. Лечится правилом «в s обязан входить старший элемент m»: перебирают подмаски числа m без старшего бита и к каждой добавляют старший бит. Проверок становится вдвое меньше, 364 вместо 665, а каждое разбиение встречается один раз.

Зачем это в работе

Задачи «разбей на группы» при малом n: разложить задания по серверам, людей по комнатам, покупки по посылкам с ограничением веса. Жадные правила там дают приближение, разбиений пятнадцати предметов на группы больше миллиарда, а таблица по маскам с подмасками даёт точный ответ за 14 миллионов проверок.

Планировщики запросов в базах данных выбирают порядок соединения таблиц тем же способом: наилучший план для множества таблиц собирается из наилучших планов для двух его частей, и в классическом варианте алгоритма части перебираются подмасками. Отсюда и практический потолок: в PostgreSQL точный перебор по умолчанию идёт, пока таблиц в запросе меньше 12, дальше включается приближённый поиск.

И сам приём s & (s - 1) - первый из семейства трюков с младшей единицей, которым посвящена следующая глава.

Теперь сам

1. Выпиши подмаски m = 1010 в том порядке, в каком их выдаёт цикл.
2. Сколько подмасок у маски 0b110110?
3. Сколько всего пар (m, s) при n = 5?
4. s = 0b10100, m = 0b11101. Найди следующую подмаску.
5. В разборе с грузами цикл для m = 0b0111 дошёл до s = 0b0101. Какую ячейку таблицы он читает?