Конспект: генерация комбинаторных объектов

Понятия

Подмножество - любой выбор части элементов, порядок не важен; всего их 2ⁿ.

Перестановка - порядок всех элементов; всего n!.

Сочетание - выбор k элементов без учёта порядка; всего C(n,k) = n!/(k!·(n−k)!).

Маска - подмножество, закодированное числом: разряд i равен единице, если элемент взят. Читается арифметикой mask // 2**i % 2 или побитово - (mask >> i) & 1.

Монотонный индекс - приём «назад не возвращаемся»: после взятия элемента i спуск идёт с i + 1. Механическая форма отказа от порядка внутри набора.

Разбиение числа - сумма без учёта порядка; перечисление по невозрастанию частей, подсчёт разменом (внешний цикл по частям). Разбиение множества - группы различных предметов; номер группы не больше «максимум + 1», число Белла.

Формула Кэли - n^(n−2) деревьев на n пронумерованных вершинах. Код Прюфера - отрезать наименьший лист, записать соседа; степень = 1 + число появлений в коде.

Что унести

ЧИСЛО ОБЪЕКТОВ ИЗ ОДНОЙ СТРОКИ КОДА
rec(i + 1, ...) из цикла с i = start      сочетания           C(n,k)
rec(i, ...)     из цикла с i = start      с повторениями      C(n+k−1, k)
rec(i + 1, ...) из цикла с i = 0          все последовательности  nᵏ
две ветки «берём / не берём»              подмножества        2ⁿ
флаг «занято» на каждый элемент           перестановки        n!

Узлов в дереве перебора - не столько же, сколько ответов: у подмножеств 2ⁿ⁺¹ − 1 (вдвое больше листьев), у перестановок около e·n! ≈ 2,72·n!. То есть накладные расходы перебора - константа, и бороться надо с числом ответов, а не с устройством обхода.

ТРИ СПОСОБА ПЕРЕБРАТЬ ПЕРЕСТАНОВКИ (замер при n = 6, у обеих рекурсий 1957 вызовов)
флаги «занято» + склейка набора     45 036 шагов   лексикографический порядок
обмен на месте, с откатом           16 889 шагов   порядок СВОЙ, не лексикографический
next_permutation без рекурсии       12 454 шага    лексикографический, без стека и без дублей

при n = 7 версия с флагами в предел шагов движка НЕ укладывается, обмен - да

ЦЕНА ВЫБОРА ПРИЁМА (одинаковый ответ, разные шаги)
сочетания C(8,4) = 70
    монотонный индекс            1583 шага
    фильтр по маске (2⁸ наборов) 9036 шагов   в 5,7 раза дороже
    сломанная монотонность       46 727 шагов и ОТВЕТ 4096

подмножества, n = 10
    рекурсия                     12 285 шагов
    счётчик по маске             41 986 шагов   в 3,4 раза дороже: n разрядов на набор

Порядок выдачи - свойство приёма, а не задачи. Рекурсия «берём первым» идёт от полного набора к пустому; счётчик по маске - от пустого, но не лексикографически (после [2, 3, 4] у него идёт [1, 2, 5]); монотонный индекс даёт лексикографический порядок сам, без сортировки. Нужен конкретный порядок - проверяй запуском на трёх элементах.

Отсечение - сделка, а не улучшение. Проверка стоит шаг на каждом узле, экономит - только на отсечённых ветках. Замер отсечения по остатку в сочетаниях: C(10,8) 63 процента выигрыша, C(10,5) семь, C(20,3) один процент ПРОИГРЫША. Мерить, а не предполагать.

Ловушки джокера

Сохранил набор, а не его копию. otvety.append(nabor) при переборе с append/pop записывает ссылку: восемь ответов на трёх элементах превращаются в восемь пустых списков. Лечится срезом nabor[:].

Забыл откат. Состояние, изменённое перед спуском (обмен, флаг, добавленный элемент), обязано быть восстановлено после возврата. Без отката программа не падает - она выдаёт не те ответы.

start объявлен и не использован. Сочетания превращаются в последовательности: 25 вместо 10 при n = 5, k = 2. Признак - число ответов похоже на степень, а не на биномиальный коэффициент.

Дубли при равных элементах. [1, 1, 2, 2] даёт 24 перестановки вместо 6. Пропуск второго экземпляра равного значения (пока свободен первый) чинит и ответ, и цену: 390 шагов вместо 1122.

Собрал все ответы в список. C(30,15) - 155 миллионов наборов, 2²⁵ - 33 миллиона. Обрабатывать надо по одному, на месте.

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

Посчитал C(n,k) через факториалы в лоб. 30! не помещается в 64-битное целое, хотя C(30,15) помещается легко. Считают произведением с делением на каждом шаге.

Куда это ведёт

Перебирать мы научились - и упёрлись в стену ровно там, где её и ждали: 2ⁿ при n = 15, n! при n = 7. Следующая глава - про то, как не раскрывать ветки, в которых ответа заведомо нет: поиск с возвратомРазбирается в разделе 16, глава «Поиск с возвратом и отсечения»: Поиск с возвратом: проверять на входе в ветку, а не на дне с проверкой на входе в ветку, отсечение по оценкеРазбирается в разделе 16, глава «Поиск с возвратом и отсечения»: Отсечения: по оценке, по симметрии и по порядку переменных и отсечение по симметрии. Выигрыш там измеряется уже не процентами, а разами - но правило «отсечение надо мерить» останется.