Коротко

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

Сколько их и почему это важно

Перестановка — это упорядочение всех элементов. Для [1, 2, 3] их шесть: на первое место можно поставить любой из трёх, на второе — любой из двух оставшихся, на третье — последний. Отсюда $3 \cdot 2 \cdot 1 = 3! = 6$. Подробнее формулы разобраны в статье про комбинаторику.

Факториал растёт очень быстро:

Поэтому в задачах «выведите все перестановки» $n$ обычно не больше 8–10. Если в условии $n$ до $10^5$, полный перебор заведомо не нужен: ищут формулу, жадность или ту самую следующую перестановку.

Ещё одно следствие: каждая перестановка — это список длины $n$, и копирование его в ответ стоит $O(n)$. Значит, любой генератор всех перестановок работает минимум за $O(n \cdot n!)$. Оптимизировать тут можно только константу и лишние ветки.

Способ 1: бэктрекинг с used[]

Самая понятная схема. Строим перестановку слева направо в списке path. На каждом шаге перебираем все элементы и берём те, что ещё не стоят в пути. Чтобы проверка была за $O(1)$, заводим массив флагов used.

def permute(nums):
    result, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result


print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Разберём, что здесь важно.

• Состояние — это пара path и used. Перед рекурсивным вызовом меняем оба, после — оба откатываем. Забытый used[i] = False даёт ровно одну перестановку вместо всех: после первого спуска все флаги остаются поднятыми.
• path[:], а не path. В ответ кладём копию. Если положить сам список, в конце все элементы result окажутся одним и тем же пустым списком, потому что path к тому моменту очищен откатами.
• Флаги по индексам, а не по значениям. Проверка if nums[i] in path тоже работает для различных чисел, но стоит $O(n)$ и ломается на повторах: второй единицы в пути никогда не будет, потому что первая уже «там».

Порядок вывода получается лексикографическим, если входной массив отсортирован: на каждом уровне мы перебираем кандидатов слева направо.

Дерево рекурсии для $n = 3$ выглядит так: корень, три ветки на первом уровне, по две на втором, по одной на третьем. Всего $1 + 3 + 6 + 6 = 16$ вызовов. На каждом вызове цикл проходит все $n$ индексов, включая занятые, поэтому общая работа — $O(n \cdot n!)$, а дополнительная память (не считая ответа) — $O(n)$ на стек, path и used.

Способ 2: обмены на месте

Можно обойтись без path и used. Идея: массив сам хранит текущую перестановку. Префикс nums[0:first] уже зафиксирован, хвост nums[first:] — это ещё не использованные элементы. На позицию first по очереди ставим каждый элемент хвоста обменом, спускаемся на уровень глубже и меняем обратно.

def permute_swap(nums):
    nums = nums[:]
    result = []

    def backtrack(first):
        if first == len(nums):
            result.append(nums[:])
            return
        for i in range(first, len(nums)):
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]

    backtrack(0)
    return result


print(permute_swap([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

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

Чем он лучше первого:

• цикл идёт только по хвосту, а не по всем $n$ индексам, поэтому на занятые элементы время не тратится;
• нет вспомогательных массивов — только стек рекурсии;
• тот же приём используется, когда перестановки нужно не собрать, а обработать на лету: например, проверить каждую и сразу выбросить.

Обратный обмен после рекурсии обязателен. Без него массив на выходе из ветки окажется не в том состоянии, в каком был на входе, и часть перестановок потеряется, а часть повторится.

Нужна копия nums[:] в начале? Строго говоря, нет: после всех откатов массив возвращается в исходный вид. Но функция, которая во время работы портит аргумент вызывающего кода, удивляет читателя, поэтому копию лучше сделать.

Permutations II: когда в массиве есть повторы

Возьмём [1, 1, 2]. Обе схемы выше выдадут шесть перестановок, и каждая из трёх различных встретится дважды: первая единица и вторая единица для алгоритма — разные элементы. Встроенный itertools.permutations ведёт себя так же.

from itertools import permutations

print(list(permutations([1, 1, 2])))
# [(1, 1, 2), (1, 2, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 1, 1)]

Различных перестановок мультимножества меньше: $\dfrac{n!}{c_1! \cdot c_2! \cdots}$, где $c_k$ — сколько раз встречается каждое значение. Для [1, 1, 2] это $\dfrac{3!}{2! \cdot 1!} = 3$.

Решение «сгенерировать всё и положить в set» правильное, но плохое: при [1, 1, 1, 1, 2, 2, 2] вы построите $7! = 5040$ перестановок, чтобы оставить 35. На собеседовании его можно назвать как первый вариант, но дальше ждут отсечения.

Сортировка и правило соседа

Отсортируем массив, чтобы одинаковые значения стояли рядом. Тогда правило такое: на одном уровне рекурсии из группы равных элементов берём только первый свободный. Записывается это одной строкой.

def permute_unique(nums):
    nums = sorted(nums)
    result, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result


print(permute_unique([1, 1, 2]))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

Почему именно not used[i - 1]? Условие означает: «предыдущая копия этого значения свободна». Если мы сейчас пропустили её и берём следующую, то на этом же уровне уже была (или будет) ветка, начинающаяся с предыдущей копии. Ветка с текущей дала бы те же самые перестановки. А если used[i - 1] истинно, предыдущая копия уже стоит в пути выше по дереву, и текущая — это законное «второе вхождение», его брать нужно.

По сути правило заставляет одинаковые значения входить в перестановку строго в порядке их индексов: сначала первая единица, потом вторая. У каждой различной перестановки ровно одна такая расстановка, поэтому дубликатов нет.

Ловушка: used[i - 1] вместо not used[i - 1]

Встречается вариант с условием used[i - 1] без not. Он тоже даёт правильный ответ: просто заставляет копии входить в обратном порядке. Но отсекает он гораздо позже, уже в глубине дерева. Мы посчитали вызовы backtrack на [1, 1, 1, 1, 2, 2, 2], где различных перестановок 35:

Разница почти в десять раз, и она растёт с числом повторов. Если на собеседовании спросят, почему not, ответ такой: мы режем ветку на том уровне, где она впервые становится дублем, а не через несколько уровней.

Вариант со счётчиком

Есть способ, где сортировка вообще не нужна. Вместо индексов перебираем различные значения и храним, сколько копий каждого ещё осталось.

from collections import Counter


def permute_unique_counter(nums):
    count = Counter(nums)
    result, path = [], []

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for x in count:
            if count[x] == 0:
                continue
            count[x] -= 1
            path.append(x)
            backtrack()
            path.pop()
            count[x] += 1

    backtrack()
    return result


print(permute_unique_counter([1, 1, 2]))

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

Здесь дубликаты не появляются в принципе: на каждом уровне каждое значение рассматривается один раз. Код проще объяснить, и в нём нет хитрого условия. Минус — порядок ответа зависит от порядка ключей в словаре (в Python это порядок первого появления), а не от сортировки.

### Дубликаты при обменах

В схеме с обменами правило соседа не работает. Обмены перемешивают хвост, и после первого же обмена он перестаёт быть отсортированным. Мы проверили: для `[0, 0, 1, 1, 2]` версия «отсортировать и пропускать `nums[i] == nums[i - 1]`» выдаёт 37 перестановок вместо 30.

Надёжный вариант — множество уже поставленных на позицию `first` значений, своё на каждом уровне:

```python
def permute_swap_unique(nums):
    nums = nums[:]
    result = []

    def backtrack(first):
        if first == len(nums):
            result.append(nums[:])
            return
        seen = set()
        for i in range(first, len(nums)):
            if nums[i] in seen:
                continue
            seen.add(nums[i])
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]

    backtrack(0)
    return result


print(permute_swap_unique([1, 1, 2]))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

seen создаётся внутри вызова, а не снаружи: запрет «это значение уже стояло на позиции first» действует только на текущем уровне.

Next Permutation: следующая по порядку

Задача LeetCode 31: переставить элементы массива так, чтобы получилась следующая в лексикографическом порядке перестановка. Если текущая последняя (массив убывает), вернуть первую — отсортированную по возрастанию. Изменять нужно на месте, память $O(1)$.

Перебором тут не обойтись: даже при $n = 20$ перестановок больше $2 \cdot 10^{18}$. Нужно понять, как устроен порядок.

Интуиция

Сравните с числами. Следующее после 1299 — это 1300: девятки в хвосте уже «максимальны», поэтому увеличивается первая цифра слева от них, а хвост сбрасывается в минимальное значение. С перестановками то же самое.

1. Хвост, который убывает справа налево, уже максимален: никакая его перестановка не даёт большего значения. Найдём самый правый индекс i, такой что nums[i] < nums[i + 1]. Всё правее i — убывающий хвост.
2. Если такого i нет, весь массив убывает, это последняя перестановка. Разворачиваем его целиком и получаем первую.
3. Иначе nums[i] нужно увеличить, но минимально. Ищем в хвосте самый правый элемент nums[j] > nums[i]. Поскольку хвост убывает, это наименьший из тех, что больше nums[i]. Меняем их местами.
4. После обмена хвост по-прежнему убывает (проверьте: nums[j] был наименьшим подходящим, и на его место встал меньший элемент). Чтобы хвост стал минимальным, разворачиваем его — получаем возрастание.

Код

def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    left, right = i + 1, len(nums) - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums


print(next_permutation([1, 3, 5, 4, 2]))  # [1, 4, 2, 3, 5]
print(next_permutation([3, 2, 1]))  # [1, 2, 3]
print(next_permutation([1, 1, 5]))  # [1, 5, 1]

Разворот хвоста — классические два указателя. Когда i = -1, разворачивается весь массив, поэтому отдельная ветка для «последней перестановки» не нужна.

Разбор на примере

Возьмём [1, 3, 5, 4, 2].

Почему строгие и нестрогие сравнения именно такие

В обоих циклах стоят нестрогие >= и <=. Это то, что делает алгоритм корректным при повторах. Если в первом цикле написать строгое >, то на [1, 2, 2] поиск спада остановится на паре равных двоек, обменять будет не с чем, и массив вернётся без изменений вместо [2, 1, 2] (а без дополнительной проверки j и вовсе уйдёт за начало массива). Если во втором цикле написать <, то на [1, 2, 1] первая единица обменяется с равной ей последней, и после разворота получится [1, 1, 2] — шаг назад вместо [2, 1, 1].

При правильных сравнениях алгоритм сам корректно обрабатывает мультимножества. Отсюда ещё один способ решить Permutations II: отсортировать массив и вызывать next_permutation, пока не вернёмся к началу. Так работает std::next_permutation в C++, и он выдаёт только различные перестановки в лексикографическом порядке.

def all_by_next(nums):
    nums = sorted(nums)
    result = [nums[:]]
    while True:
        next_permutation(nums)
        if nums == result[0]:
            return result
        result.append(nums[:])


print(all_by_next([1, 1, 2]))
# [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

(Функция использует next_permutation из предыдущего блока.) Это итеративный генератор без рекурсии: удобно, если стек ограничен или нужно останавливаться и продолжать с того же места.

Сложность одного шага — $O(n)$ в худшем случае, памяти $O(1)$. В среднем шаг стоит $O(1)$: длинные убывающие хвосты встречаются редко.

Тот же алгоритм на JavaScript:

function nextPermutation(nums) {
  let i = nums.length - 2
  while (i >= 0 && nums[i] >= nums[i + 1]) i--
  if (i >= 0) {
    let j = nums.length - 1
    while (nums[j] <= nums[i]) j--
    ;[nums[i], nums[j]] = [nums[j], nums[i]]
  }
  for (let l = i + 1, r = nums.length - 1; l < r; l++, r--) {
    ;[nums[l], nums[r]] = [nums[r], nums[l]]
  }
  return nums
}

console.log(nextPermutation([1, 3, 5, 4, 2])) // [ 1, 4, 2, 3, 5 ]
console.log(nextPermutation([3, 2, 1])) // [ 1, 2, 3 ]

Бонус: k-я перестановка без перебора

Задача LeetCode 60 (Permutation Sequence): дано $n$ и $k$, вернуть $k$-ю по порядку перестановку чисел $1..n$. Звать next_permutation $k$ раз слишком долго, когда $k$ порядка $n!$.

Наблюдение: перестановки, начинающиеся с одной и той же цифры, идут блоками по $(n-1)!$. Значит, первая цифра определяется как (k - 1) // (n - 1)!, остаток передаётся дальше. Это факториальная система счисления.

from math import factorial


def get_permutation(n, k):
    digits = [str(d) for d in range(1, n + 1)]
    k -= 1
    result = []
    for pos in range(n, 0, -1):
        block = factorial(pos - 1)
        index, k = divmod(k, block)
        result.append(digits.pop(index))
    return ''.join(result)


print(get_permutation(3, 3))  # 213
print(get_permutation(4, 9))  # 2314

Для $n = 4$, $k = 9$: $k - 1 = 8$, блок $3! = 6$, индекс $1$ — первая цифра 2, остаток $2$. Дальше блок $2! = 2$, индекс $1$ среди [1, 3, 4] — цифра 3, остаток $0$. Оставшиеся 1, 4 идут по порядку: 2314. Сложность $O(n^2)$ из-за pop из середины списка, для $n \le 9$ это мгновенно.

Какой способ выбрать

Про itertools и его ленивые генераторы есть отдельная статья. На собеседовании его обычно просят не использовать, но упомянуть стоит.

Типичные ошибки

• Кладут в ответ path, а не копию. В конце все элементы ответа указывают на один пустой список.
• Откатывают не всё. В схеме с used[] два изменения — path и флаг, в схеме с обменами — сам обмен. Каждое нужно вернуть.
• Проверяют x in path вместо флагов. Медленнее и неверно при повторах.
• Забывают отсортировать перед правилом соседа. Условие nums[i] == nums[i - 1] имеет смысл, только если равные элементы стоят рядом.
• Переносят правило соседа в схему с обменами. Хвост там не отсортирован, дубли проскакивают.
• В Next Permutation путают строгие и нестрогие сравнения. На массивах с повторами алгоритм возвращает тот же массив, шагает назад или выходит за границы.
• В Next Permutation забывают развернуть хвост или сортируют его за $O(n \log n)$. Хвост уже убывает, разворот достаточен и стоит $O(n)$.

Что спрашивают на собеседованиях

Типичная цепочка выглядит так: сначала Permutations (LeetCode 46), затем вопрос «а если есть повторы?» — это Permutations II (47). Дальше могут спросить про сложность и попросить объяснить, почему нельзя быстрее $O(n \cdot n!)$. Отдельной задачей часто дают Next Permutation (31): она короткая, но проверяет, умеете ли вы рассуждать о порядке, а не просто писать рекурсию. Близкая к ней Next Greater Element III (556) — та же идея применительно к цифрам числа.

Хорошее продолжение после перестановок — комбинации. В них порядок не важен, поэтому вместо used[] передают индекс start, и элементы берутся только правее него. Это хорошо видно в разборе Combination Sum, а саму задачу можно решить в тренажёре. Если рекурсия пока даётся тяжело, начните со статьи про рекурсию, а оценку сложности освежите в материале про Big O.

Что запомнить

1. Все перестановки — это $n!$ ответов, поэтому $O(n \cdot n!)$ — нижняя граница, и $n$ в таких задачах маленькое.
2. used[] и обмены — два равноправных способа. Первый сохраняет лексикографический порядок, второй экономит память.
3. Повторы убираются на этапе генерации: сортировка и not used[i - 1] или счётчик значений. set в конце — только как первый наивный вариант.
4. Next Permutation: спад справа, обмен с ближайшим большим, разворот хвоста. С нестрогими сравнениями он работает и на повторах.