Подмножества: дерево «берём - не берём» и счётчик по маске

Если ты уже писал и рекурсию «берём - не берём», и перебор по маске, и знаешь, чем их порядок отличается, - листай до «Теперь сам».

Как думаешь, сколько подмножеств у двадцати элементов

На складе двадцать товаров. Нужно перебрать все наборы, которые можно собрать из них в коробку: пустую коробку, каждый товар по отдельности, все пары, все тройки и так до полного набора.

Прежде чем читать дальше, ответь себе на два вопроса. Сколько всего получится наборов? И если проверка одного набора занимает микросекунду, успеет ли программа за время, пока ты пьёшь чай?

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

Представь ряд выключателей на стене - по одному на каждый товар. Любое положение всех выключателей сразу и есть один набор: щёлкнутые вверх товары в коробке, остальные нет. Вопрос «сколько наборов» превращается в вопрос «сколько разных положений у двадцати выключателей», а это уже школьная комбинаторика: каждый независимо в двух состояниях, значит 2²⁰ - это 1 048 576, чуть больше миллиона. При микросекунде на набор выходит около секунды: чай остыть не успеет. Но запомни, как это число получилось, - каждый следующий товар его удваивает.

Вторая половина аналогии тоже работает. Если занумеровать положения выключателей как двоичное число - верхний выключатель единица, нижний ноль, - то перебрать все наборы значит просто посчитать от нуля до 2²⁰ − 1. Именно так и устроен второй способ.

Механизм: дерево решений, у которого ровно 2ⁿ листьев

Перебор подмножеств удобно видеть как дерево. На каждом уровне решается судьба ОДНОГО элемента: левая ветка - не берём, правая - берём. Уровней столько, сколько элементов, поэтому путь от корня до листа - это одно решение по каждому элементу, то есть одно подмножество.

Из картинки сразу видно, откуда берётся число вызовов. Полное двоичное дерево глубины n имеет 1 + 2 + 4 + ... + 2ⁿ узлов, а эта сумма равна 2ⁿ⁺¹ − 1 - её мы считали в разделе про суммы. Половина узлов - листья, то есть на каждый готовый ответ приходится примерно один промежуточный вызов, и накладные расходы перебора в этой задаче невелики.

Правило

Подмножеств у n элементов ровно 2ⁿ: решение по каждому элементу независимо, и ветвление удваивает число вариантов на каждом уровне. Перечислить все подмножества можно двумя равноценными способами. Рекурсия «берём - не берём»: функция получает номер элемента и уже собранный набор, вызывает себя дважды и на дне записывает ответ; цена - 2ⁿ⁺¹ − 1 вызовов. Счётчик по маске: номер набора идёт от 0 до 2ⁿ − 1, элемент i входит в набор, если в разряде i этого номера стоит единица (mask // 2**i % 2 == 1); рекурсии нет, памяти нужно столько же, сколько на один набор. Порядок выдачи у способов РАЗНЫЙ, и если порядок важен - его надо проверять, а не предполагать.

Разбор: рекурсия на трёх элементах - 15 вызовов и 8 ответов

Код целиком. Параметр i - номер элемента, судьба которого решается сейчас; vzyato - то, что уже набрано:

def rec(i, vzyato):
    if i == len(a):
        print(vzyato)
        return 0
    rec(i + 1, vzyato + [a[i]])   # берём элемент a[i]
    rec(i + 1, vzyato)            # не берём
    return 0

rec(0, [])

Запуск на a = [1, 2, 3] печатает восемь строк в таком порядке:

[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]

Замер движка на этом прогоне: 65 шагов и 15 вызовов. Пятнадцать - это ровно 2⁴ − 1, то есть все узлы дерева с картинки, включая восемь листьев. Проверка на большем n даёт ту же формулу: при n = 10 - 2047 вызовов, при n = 14 - 32 767.

Порядок стоит разобрать отдельно, потому что он удивляет. Первой вышла не пустая коробка, а полная: на схеме это самый ПРАВЫЙ лист 111, и дальше код идёт по листьям справа налево, до 000. Причина в строке rec(i + 1, vzyato + [a[i]]), которая стоит ПЕРВОЙ: рекурсия всегда сначала доходит до дна по «берём», и только потом разворачивается. Поменяй две строки местами - и порядок станет обратным, от пустого набора к полному. Ни один из порядков не лучше, но про оба надо знать: от порядка зависит, какой ответ программа найдёт первым, а в следующих главах это станет важно.

Разбор: тот же перебор счётчиком, и почему его порядок другой

Рекурсия не обязательна. Если набор - это набор нулей и единиц, то перебрать наборы значит перебрать числа:

mask = 0
while mask < 2 ** len(a):
    nabor = []
    i = 0
    while i < len(a):
        if mask // 2 ** i % 2 == 1:
            nabor.append(a[i])
        i = i + 1
    print(nabor)
    mask = mask + 1

Выражение mask // 2 ** i % 2 - это «какая цифра стоит в разряде i двоичной записи mask»: деление на 2**i сдвигает запись на i разрядов вправо, остаток от деления на 2 оставляет младшую цифру. То же пишут побитово - (mask >> i) & 1, - и это дешевле; побитовые операции разбирает раздел про битовые приёмыРазбирается в разделе 19, глава «Маски, сдвиги и множество на битах»: Шесть операций над битами: И, ИЛИ, исключающее ИЛИ, НЕ и два сдвига, а до него маски в курсе читаются арифметикой.

Тот же запуск на a = [1, 2, 3]:

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

Сравни с выводом рекурсии выше: наборы те же восемь, а порядок другой. Счётчик идёт по возрастанию НОМЕРА маски, а в номере младший разряд отвечает за первый элемент, поэтому [2] выходит раньше, чем [1, 2], а [3] - раньше, чем [1, 3]. Рекурсия «берём первым» идёт по убыванию той же двоичной записи, читаемой с другого конца. Если задача требует определённого порядка, его надо задавать явно, а не надеяться на способ перебора.

За удобство счётчика приходится платить лишней работой: он на каждый набор прогоняет внутренний цикл по всем n разрядам, даже если набор пустой. Замер на наборе из десяти элементов: счётчик 41 986 шагов против 12 285 у рекурсии - в 3,4 раза дороже. Рекурсия на каждый набор тратит в среднем два вызова и две склейки, а счётчик - десять проверок разряда, и с ростом n этот разрыв растёт: при n = 3 он двукратный (134 шага против 65), при n = 12 уже 3,7 (196 610 против 53 245).

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

Первое и самое частое: сохранить сам список, а не его копию. Вариант с append и pop экономит память, но на дне надо записать именно копию:

def rec(i):
    if i == len(a):
        otvety.append(nabor)       # ОШИБКА: это ссылка на тот же список
        return 0
    rec(i + 1)
    nabor.append(a[i])
    rec(i + 1)
    nabor.pop()
    return 0

nabor = []
otvety = []
rec(0)
print(otvety)

На трёх элементах такая программа печатает [[], [], [], [], [], [], [], []] - восемь пустых списков. Число ответов верное, сами ответы потеряны: все восемь записей смотрят на один и тот же nabor, а к концу работы он снова пуст. Лечится срезом: otvety.append(nabor[:]). Замер: с append/pop и копией на дне перебор при n = 14 стоит 163 837 шагов против 229 373 у версии со склейкой vzyato + [a[i]] - в 1,4 раза дешевле, потому что склейка копирует набор на КАЖДОМ уровне, а не только на дне.

Второе: забыть, что ответов 2ⁿ, и собрать их все в список. При n = 25 это 33 миллиона наборов в памяти. Если ответы нужны не все сразу, а по одному, их надо обрабатывать на месте - в той самой строке, где сейчас стоит print.

Третье: пересчитывать 2 ** len(a) в условии цикла. Степень там считается заново на каждой из 2ⁿ проверок, и вынести её в переменную до цикла - правильная привычка. Но вот замер, который стоит знать про сам движок. Мерили программу из «Теперь сам» ниже (она считает суммы, а не печатает наборы): со степенью прямо в условии прогон при n = 12 стоит 196 622 шага, а с вынесенной границей - 196 623, то есть на один шаг БОЛЬШЕ (лишняя строка присваивания). Движок берёт плату за просмотр данных и за выполненные операторы, а не за арифметику внутри выражения. В настоящем Python экономия есть, здесь её не видно - и это полезная граница модели стоимости: замер показывает цену обхода данных, а не цену каждой машинной операции.

Четвёртое: упереться в предел и решить, что программа сломана. При n = 15 рекурсивный перебор подмножеств (а счётчик по маске - уже при n = 13) не укладывается в 300 000 шагов движка и честно об этом сообщает. Это не ошибка в коде: столько работы и заказано. Лечится не отладкой, а сокращением перебора - ровно тем, чему посвящён весь этот раздел.

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

Перебор подмножеств - это ответ на вопрос «какую комбинацию опций включить». Три сюжета из практики.

Первый: подбор конфигурации. У системы восемь независимых флагов, и надо найти набор, при котором тесты зелёные, а скорость максимальна. Это 2⁸ = 256 прогонов - вполне посильно, и такой перебор пишется за десять минут вместо недели размышлений.

Второй: тестирование. «Проверить все сочетания параметров запроса» - это тот же перебор подмножеств по списку необязательных параметров. Полезно заранее посчитать, сколько их выйдет: при двенадцати параметрах это 4096 запросов, что ещё терпимо, а при двадцати - миллион, и тест надо строить иначе.

Третий, самый важный: умение сказать «нет». Когда кто-то предлагает «просто перебрать все варианты распределения сорока задач по двум серверам», ответ считается в уме: 2⁴⁰ - это больше 10¹² вариантов, то есть восемнадцать минут при наносекунде на вариант и почти две недели при микросекунде. Это не повод сдаваться - это повод взять отсечения из следующей главы или динамику из прошлого раздела.

Теперь сам

Программа должна напечатать число подмножеств списка a, сумма элементов которых равна S. Элементы могут повторяться, и повторяющиеся элементы считаются разными. Напиши перебор по маске и скажи, на каком n он перестанет укладываться в 300 000 шагов движка.

podoshlo = 0
mask = 0
granica = 2 ** len(a)
while mask < granica:
    summa = 0
    i = 0
    while i < len(a):
        if mask // 2 ** i % 2 == 1:
            summa = summa + a[i]
        i = i + 1
    if summa == S:
        podoshlo = podoshlo + 1
    mask = mask + 1
print(podoshlo)