Перестановки: n! и почему обмен на месте дешевле флагов

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

Как думаешь, во сколько раз перестановок больше, чем подмножеств

Двадцать городов, надо объехать все и вернуться. Маршрут - это порядок, в котором города посещаются, то есть перестановка.

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

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

Представь, что рассаживаешь двадцать гостей за длинный стол. Первое место можно отдать любому из двадцати. Второе - любому из девятнадцати оставшихся. Третье - из восемнадцати. Умножаем: 20 · 19 · 18 · ... · 1, и это и есть 20!.

Разница с подмножествами видна прямо в этой сцене. Выбор «брать или не брать» не уменьшает запас: каждый следующий элемент снова решается двумя способами. А выбор «кого посадить следующим» запас съедает - зато первых вариантов сразу двадцать, а не два. Вот эти двадцать и дают взрывной рост.

Механизм: дерево, у которого ветвление убывает

Дерево перебора перестановок устроено иначе, чем дерево подмножеств. Там из каждого узла выходило ровно две ветки; здесь из корня выходит n ветвей, с первого уровня - n − 1, со второго - n − 2, и на дне ветвление кончается.

Число узлов полезно уметь считать: это 1 + n + n(n−1) + n(n−1)(n−2) + ..., то есть сумма n!/(n−k)! по всем уровням k. Если вынести n!, останется 1/0! + 1/1! + ... + 1/n! - начало того самого ряда, который сходится к числу e ≈ 2,718. Значит узлов примерно 2,72·n!. Проверка счётчиком вызовов движка: 16 при n = 3, 65 при n = 4, 326 при n = 5, 1957 при n = 6 - и 720 · 2,71805... = 1957 ровно.

Правило

Перестановок у n элементов ровно n!, а узлов в дереве их перебора около e·n! ≈ 2,72·n!, то есть меньше трёх вызовов на готовый ответ. Три способа перечисления дают один и тот же набор ответов и разные свойства. Флаги «занято» (zanyato[i]) выдают перестановки в ЛЕКСИКОГРАФИЧЕСКОМ порядке, если исходный список отсортирован. Обмен на месте (a[k], a[i] = a[i], a[k] перед спуском и назад после) не копирует набор вовсе и потому дешевле (в 2,7 раза при n = 6, и разрыв растёт с n), но порядок выдачи у него НЕ лексикографический. Итеративная «следующая перестановка» идёт лексикографически и обходится без рекурсии и без лишней памяти. Если в списке есть равные элементы, оба рекурсивных способа выдают дубли, и убираются они пропуском: на одном уровне не брать второй экземпляр равного значения, пока не взят первый. «Следующая перестановка» дублей не даёт сама.

Разбор: флаги против обмена на шести элементах

Версия с флагами. Массив zanyato помнит, какие элементы уже стоят в собранной части:

def rec(sobrano):
    if len(sobrano) == len(a):
        print(sobrano)
        return 0
    i = 0
    while i < len(a):
        if zanyato[i] == 0:
            zanyato[i] = 1
            rec(sobrano + [a[i]])
            zanyato[i] = 0
        i = i + 1
    return 0

zanyato = [0] * len(a)
rec([])

Версия с обменом. Собранная часть - это первые k элементов самого списка a; чтобы поставить на место k элемент с места i, их меняют местами, а после возврата из рекурсии обмен откатывают:

def rec(k):
    if k == len(a):
        print(a)
        return 0
    i = k
    while i < len(a):
        a[k], a[i] = a[i], a[k]
        rec(k + 1)
        a[k], a[i] = a[i], a[k]   # откат: без него список испортится
        i = i + 1
    return 0

rec(0)

Замер на одинаковых данных, вызовы совпадают до единицы, а шаги - нет:

n   вызовов   флаги, шагов   обмен, шагов   во сколько дешевле
3        16            231            134         1,7
4        65           1122            557         2,0
5       326           6561           2810         2,3
6      1957          45036          16889         2,7
7     13700      не уложился        118256          -

Причин две, и обе видны в коде. Главная - строка rec(sobrano + [a[i]]): она создаёт НОВЫЙ список на каждом узле дерева, и копирование стоит столько, сколько в наборе элементов. Обмен не создаёт ничего: он переставляет два значения в уже существующем списке. Вторая причина - цикл: у флагов он на каждом узле проходит все n позиций и проверяет zanyato[i], у обмена идёт только от k, по свободным. Поэтому разрыв растёт с n: от 1,7 раза до 2,7. На n = 7 это решает: версия с флагами не укладывается в предел шагов движка, версия с обменом укладывается.

Разбор: за что заплачено, или почему обмен портит порядок

Запусти обе версии на a = [1, 2, 3] и сравни вывод:

флаги:  [1,2,3]  [1,3,2]  [2,1,3]  [2,3,1]  [3,1,2]  [3,2,1]
обмен:  [1,2,3]  [1,3,2]  [2,1,3]  [2,3,1]  [3,2,1]  [3,1,2]

Первые четыре совпадают, последние две переставлены. Причина механическая: обмен меняет порядок ОСТАВШИХСЯ элементов. Когда на первое место ставится тройка, обмен приводит список к [3, 2, 1], и дальше перебираются перестановки хвоста [2, 1] - то есть сначала [3, 2, 1], а уже потом [3, 1, 2]. Флаги хвост не трогают: там по-прежнему 1, 2.

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

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

Первое: забыть откат. Без второй строки a[k], a[i] = a[i], a[k] список после возврата остаётся перевёрнутым, и дальше перебираются перестановки не того хвоста. Программа не падает, ответов столько же, но часть повторяется, а часть теряется. Это главный класс ошибок всего раздела: состояние, изменённое перед спуском, обязано быть восстановлено после.

Второе: дубли при равных элементах. На a = [1, 1, 2] и флаги, и обмен выдают шесть строк - [1, 1, 2], [1, 2, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 1, 1] - хотя разных перестановок только три. Разных всегда n! делённое на произведение факториалов кратностей: для [1, 1, 2, 2] это 4!/(2!·2!) = 6, а перебор выдаёт 24. В версии с флагами лечится проверкой на входе в ветку: список отсортирован, и второй экземпляр равного значения не берётся, пока не взят первый. Проверка ставится первой строкой в теле цикла, перед if zanyato[i] == 0:

    while i < len(a):
        if i > 0 and a[i] == a[i - 1] and zanyato[i - 1] == 0:
            i = i + 1          # равный предшественник свободен - эта ветка уже была
            continue
        if zanyato[i] == 0:
            ...                # дальше без изменений

Замер: на [1, 1, 2, 2] версия без проверки стоит 1122 шага и печатает 24 строки, версия с проверкой - 390 шагов и 6 строк. То есть пропуск дубля не только убирает мусор из ответа, но и почти втрое сокращает перебор. Версии с обменом этот приём не подходит: флагов у неё нет, а список после обменов не остаётся отсортированным. Там на каждом уровне запоминают, какие ЗНАЧЕНИЯ уже ставились на место k, и не ставят то же значение второй раз. А итеративная «следующая перестановка» из «Теперь сам» дублей не выдаёт вовсе: на [1, 1, 2] она печатает ровно три строки.

Третье: собирать ответы в версии с обменом строкой otvety.append(a). Печать print(a) работает верно - она снимает список в момент вызова. А вот append(a) кладёт ссылку: список a один, после возврата он восстановится, и все записи покажут исходный порядок. Если перестановки нужно собрать, на дне надо записывать копию - otvety.append(a[:]), та же ловушка, что в прошлом уроке.

Четвёртое: путать n! и 2ⁿ при оценке. При n = 10 это тысяча против трёх с половиной миллионов - разница уже в три с половиной тысячи раз, при n = 20 это миллион против 2,4·10¹⁸, то есть в два с лишним триллиона раз. Задачу на подмножества иногда можно добить перебором; задачу на перестановки - почти никогда.

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

Перестановки появляются там, где важен ПОРЯДОК. Три сюжета.

Первый: порядок обработки. «В каком порядке запускать пять миграций, чтобы ни одна не упала» - это перебор перестановок с проверкой; при пяти шагах это 120 вариантов, и такой скрипт пишется за вечер. При двенадцати шагах это 479 миллионов, и нужен уже топологический порядок из раздела про графы.

Второй: маршруты. Коммивояжёр из прошлого раздела - это перебор (n−1)! маршрутов. Умение сказать «для пятнадцати городов это 14!, почти 10¹¹ вариантов, берём динамику по маскам» - результат ровно этого урока.

Третий, неожиданный: проверка чужих алгоритмов. Перебор перестановок - это эталон, с которым сравнивают быстрое решение на маленьких данных. Так в разделе про жадность искали контрпримеры: быстрый алгоритм против полного перебора на всех входах до пяти элементов. Полный перебор там медленный, но ПРАВИЛЬНЫЙ, а на пяти элементах его цена - 120 вариантов.

Теперь сам

Нужно напечатать перестановки списка a в лексикографическом порядке, но без рекурсии вовсе. Как получить следующую перестановку из текущей?

def sleduyushchaya(p):
    i = len(p) - 2
    while i >= 0 and p[i] >= p[i + 1]:
        i = i - 1                      # ищем последний подъём
    if i < 0:
        return []                      # перестановка последняя
    j = len(p) - 1
    while p[j] <= p[i]:
        j = j - 1                      # ищем, чем заменить p[i]
    p[i], p[j] = p[j], p[i]
    l = i + 1
    r = len(p) - 1
    while l < r:                       # хвост переворачиваем
        p[l], p[r] = p[r], p[l]
        l = l + 1
        r = r - 1
    return p

p = a                                  # a отсортирован - это первая перестановка
while len(p) > 0:
    print(p)
    p = sleduyushchaya(p)              # функция переставляет p на месте