Сочетания: монотонный индекс вместо фильтра

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

Как думаешь, чем сочетание отличается от перестановки механически

У тебя восемь серверов, надо выбрать четыре под новый сервис. Набор {1, 3, 5, 7} и набор {7, 5, 3, 1} - это один и тот же выбор или два разных?

Ответ очевиден: один. А теперь вопрос, из которого растёт весь урок. Перебор перестановок выдал бы эти два набора как разные, и так же поступил бы с остальными 4! = 24 порядками той же четвёрки. Что надо изменить в переборе, чтобы каждая четвёрка вышла РОВНО ОДИН раз? Подумай, прежде чем читать дальше: где именно в коде живёт «порядок», от которого надо избавиться?

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

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

«Назад не возвращаемся» - это и есть монотонный индекс. Порядок внутри набора не исчезает по волшебству: он просто фиксируется один раз - по возрастанию номера.

Механизм: один параметр вместо фильтра

У функции перебора появляется параметр start: номер, начиная с которого разрешено брать элементы. Взяли элемент i - спускаемся с start = i + 1, и все элементы левее i становятся недоступны навсегда.

def rec(start, nabor):
    if len(nabor) == k:
        print(nabor)
        return 0
    i = start
    while i < len(a):
        rec(i + 1, nabor + [a[i]])
        i = i + 1
    return 0

rec(0, [])

Сколько получится ответов, видно из той же картинки: каждая пара - и вообще каждый набор - собирается ровно одним путём, значит листьев-ответов ровно C(n,k): здесь шесть, а для четвёрок из восьми серверов - семьдесят. Тупик «4» ответом не считается: в нём набор так и остался из одного элемента. А формула C(n,k) = n!/(k!·(n−k)!) читается прямо из сравнения с перестановками: упорядоченных наборов по k элементов n!/(n−k)!, каждый набор среди них встречается k! раз во всех порядках, поэтому делим на k!. Монотонность и есть механическая форма этого деления.

Правило

Сочетание - выбор k из n без учёта порядка, число сочетаний C(n,k) = n!/(k!·(n−k)!). Перебор сочетаний отличается от перебора последовательностей одним параметром: функция получает start - номер, с которого разрешено брать, - и после взятия элемента i спускается с i + 1. Это монотонность индекса, и она выбрасывает ровно k! порядков каждого набора. Замени i + 1 на i - получится перебор сочетаний С ПОВТОРЕНИЯМИ, их C(n+k−1, k). Замени start на 0 - получится перебор всех nᵏ последовательностей. Фильтровать подмножества по размеру (2ⁿ вариантов с проверкой «ровно k единиц») тоже можно, но это дороже в разы и даёт другой порядок.

Разбор: три версии на восьми серверах, выбрать четыре

Правильный ответ - C(8,4) = 70. Теперь три программы, которые его считают, и их цена по движку. Чтобы сравнение было честным, все три наборы не печатают, а СЧИТАЮТ: на дне стоит otvety.append(nabor) вместо print, в конце - print(len(otvety)). Склейка nabor + [a[i]] создаёт новый список на каждом вызове, поэтому ловушки со ссылкой из первого урока тут нет. Фильтр по маске - это счётчик из того же урока с одной добавкой: набор идёт в счёт, только если в нём ровно k элементов (код - в «Теперь сам»).

версия                                          ответ   шагов   вызовов
монотонный индекс: rec(i + 1, ...)                 70    1583       163
сломанная монотонность: i = 0 вместо start       4096   46727      4681
фильтр по маске: 2⁸ наборов, проверка размера       70    9036         0

Сломанная версия дала 8⁴ = 4096 - все последовательности из четырёх номеров, включая [1,1,1,1] и все 24 порядка каждой честной четвёрки. Ошибка выглядит безобидно: start в коде есть, он просто не используется в цикле. Ответ при этом неверный в 58 раз, и программа об этом не сообщает.

Фильтр по маске отвечает верно и платит за это шестикратной ценой: он проходит все 256 подмножеств и отбрасывает 186 из них, посчитав у каждого число единиц. Чем сильнее k отличается от n/2, тем хуже: при n = 12, k = 3 фильтр перебирает 4096 наборов ради 220 ответов - 200 930 шагов движка против 2677 у монотонного перебора на той же задаче, то есть в 75 раз дороже.

Разбор: отсечение, которое то спасает, то мешает

Из картинки видно, что часть ветвей заведомо пустая: если осталось меньше элементов, чем нужно добрать, ответа в этой ветке нет. Проверка пишется в одну строку:

def rec(start, nabor):
    if len(nabor) == k:
        otvety.append(nabor)
        return 0
    if len(a) - start < k - len(nabor):
        return 0                 # добрать уже не из чего
    i = start
    while i < len(a):
        rec(i + 1, nabor + [a[i]])
        i = i + 1
    return 0

Выглядит как явное улучшение. Замер говорит иначе:

задача        без отсечения   с отсечением   выигрыш
C(5,3)                  227            223        2%
C(8,4)                 1583           1524        4%
C(10,5)                6774           6282        7%
C(10,8)               12066           4446       63%
C(20,3)               12137          12298    −1%, стало ДОРОЖЕ

Объяснение простое, и его стоит запомнить на весь раздел. Отсечение стоит шаг на КАЖДОМ узле, а экономит только на тех ветках, которые действительно упираются в нехватку остатка. При k, близком к n, таких ветвей большинство: чтобы набрать восемь из десяти, пропустить можно всего два элемента, и почти любая ветка, начатая не с самого левого края, обречена. Отсюда 63% на C(10,8) - узлов стало 375 вместо 1013. При k около половины выигрыш скромный, 7%. При k, сильно меньшем n, тупиков почти нет: взять три элемента из двадцати можно откуда угодно, и проверка просто берёт плату, ничего не отсекая. Отсюда минус один процент на C(20,3).

Отсечение - это сделка, а не улучшение. Платишь на каждом узле, получаешь на отсечённых ветках, и выгода зависит от данных. Следующая глава про отсечения целиком, и там выигрыш будет измеряться не процентами, а разами - но правило «мерить, а не предполагать» останется тем же.

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

Первое: start объявлен и не использован. Самая частая ошибка, и мы её только что посчитали: ответ больше настоящего в k! раз и даже больше, потому что добавляются наборы с повторами. Признак на проверке - число ответов выглядит как степень, а не как биномиальный коэффициент.

Второе: rec(i, ...) вместо rec(i + 1, ...). Одна правка, и задача меняется на сочетания с повторениями: при n = 10, k = 5 ответ 2002 вместо 252. Иногда это именно то, что нужно (выбрать пять шариков из десяти цветов, цвета могут повторяться), и тогда формула другая: C(n+k−1, k). Откуда она: такой выбор - это строка из k шариков и n − 1 перегородок между цветами, и набор задаётся тем, на каких k местах из n + k − 1 стоят шарики. Проверка: C(14, 5) = 2002. Проверять такой перебор надо на маленьком примере, где ответ известен руками.

Третье: собирать все сочетания в список при больших n. C(30,15) - это 155 миллионов наборов. Обрабатывать их надо по одному, на месте.

Четвёртое: считать C(n,k) через факториалы в лоб. 30! - число из 33 цифр, хотя сам C(30,15) всего девятизначный. Python такое переживёт, его целые не переполняются, но в языках с 64-битными целыми 30! просто не поместится и ответ выйдет мусорным. Считают произведением с делением на каждом шаге: начать с c = 1 и для j от 0 до k − 1 повторять c = c * (n - j) // (j + 1).

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

Первый сюжет: тестовые наборы. «Проверить все пары параметров» - это C(n,2), «все тройки» - C(n,3). Разница практическая: при двадцати параметрах пар 190, троек 1140, а четвёрок уже 4845. Отсюда и берутся промышленные стратегии тестирования «все пары», а не «все комбинации».

Второй: выбор подмножества ресурсов. «Какие четыре из восьми узлов вывести в обслуживание, чтобы кластер остался живым» - перебор из 70 вариантов, посчитать можно на месте и честно, без эвристик.

Третий: оценка в разговоре. Когда кто-то говорит «переберём все сочетания», надо вслух назвать число. C(50,5) - это два миллиона, нормально. C(50,10) - десять миллиардов, уже нет. Знать формулу значит отличать первое от второго до того, как написан код.

Теперь сам

Напиши перебор, который печатает все сочетания по k из списка a в лексикографическом порядке, и объясни, почему фильтр по маске тут не подойдёт.

def rec(start, nabor):
    if len(nabor) == k:
        print(nabor)
        return 0
    i = start
    while i < len(a):
        rec(i + 1, nabor + [a[i]])
        i = i + 1
    return 0

rec(0, [])

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
    if len(nabor) == k:          # вся разница со счётчиком из первого урока
        print(nabor)
    mask = mask + 1