Следующая перестановка: алгоритм Нараяны и k-я перестановка
LeetCode 31 Next Permutation за O(n) на месте: алгоритм Нараяны с доказательством, предыдущая перестановка, k-я перестановка (LeetCode 60) и ранг через факториальную систему.
Коротко
| Вопрос | Ответ |
|---|---|
| Что делает Next Permutation | Переставляет массив в следующую по лексикографическому порядку перестановку, а последнюю — в первую |
| Алгоритм | Найти справа первый спад nums[i] < nums[i+1], обменять nums[i] с ближайшим большим справа, развернуть хвост |
| Сложность | в худшем случае, в среднем на шаг, память |
| k-я перестановка (LC 60) | Записать в факториальной системе счисления: цифры — индексы среди ещё не взятых чисел |
| Обратная задача | Ранг перестановки: сколько меньших чисел стоит правее каждой позиции, умножить на факториалы |
В статье про перестановки Next Permutation — один из разделов среди бэктрекинга и обработки дубликатов. Здесь разберём только порядок перестановок: почему алгоритм даёт именно следующую перестановку, как его развернуть в обратную сторону, почему шаг в среднем стоит константу и как прыгнуть сразу к -й перестановке или, наоборот, узнать номер данной.
Лексикографический порядок и аналогия со счётчиком
Перестановки сравниваются как слова в словаре: по первому различающемуся элементу. Для [1, 2, 3] порядок такой:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Первая перестановка отсортирована по возрастанию, последняя — по убыванию. Задача LeetCode 31 просит по текущей перестановке получить следующую, изменив массив на месте и используя дополнительной памяти. Если перестановка последняя, нужно вернуть первую.
Лучшая интуиция — прибавление единицы к числу. После 1299 идёт 1300: девятки в хвосте уже максимальны, увеличить их нельзя, поэтому растёт первая цифра левее них, а хвост сбрасывается в минимум — нули. Если вы решали задачу Plus One, это ровно её логика с переносом.
У перестановки «максимальный хвост» — это хвост, убывающий слева направо: никакая его перестановка не больше его самого. Значит, нужно найти самую правую позицию, которую ещё можно увеличить, увеличить её минимально и сбросить хвост в минимальное состояние — по возрастанию.
Наивное решение
Сгенерировать все перестановки, отсортировать, найти текущую и взять следующую. Это времени и столько же памяти. Уже при перестановок почти полмиллиарда, при — больше . На собеседовании такой вариант стоит только назвать, чтобы показать, от чего отталкиваетесь.
Алгоритм Нараяны
Алгоритм известен давно: Дональд Кнут в «Искусстве программирования» (том 4A, раздел о генерации перестановок) возводит его к индийскому математику Нараяне Пандиту, XIV век. В русскоязычной литературе его так и называют — алгоритм Нараяны. Шаги:
- Найти спад. Идём справа налево и ищем самый правый индекс
i, для которогоnums[i] < nums[i + 1]. Всё правееiубывает (нестрого). Если такогоiнет, массив целиком убывает — это последняя перестановка. - Найти замену. В хвосте справа ищем самый правый
j, для которогоnums[j] > nums[i]. Хвост убывает, поэтому самый правый подходящий элемент — наименьший из тех, что большеnums[i]. - Обменять
nums[i]иnums[j]. - Развернуть хвост
nums[i + 1:]. Он по-прежнему убывает, после разворота станет возрастающим, то есть минимальным.
Если на шаге 1 спада нет, i = -1, шаги 2–3 пропускаются, а разворот «хвоста с позиции 0» переворачивает весь массив в первую перестановку. Отдельная ветка не нужна.
def next_permutation(nums): n = len(nums) i = n - 2 while i >= 0 and nums[i] >= nums[i + 1]: i -= 1 if i >= 0: j = n - 1 while nums[j] <= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] left, right = i + 1, n - 1 while left < right: nums[left], nums[right] = nums[right], nums[left] left += 1 right -= 1 a = [1, 2, 3, 4] for _ in range(3): next_permutation(a) print(a) # [1, 2, 4, 3] # [1, 3, 2, 4] # [1, 3, 4, 2]
Разворот — обычные два указателя, навстречу друг другу. В LeetCode функция ничего не возвращает: проверяется сам массив.
Разбор на примере
Возьмём [2, 4, 7, 6, 3, 1].
| Шаг | Массив | Что происходит |
|---|---|---|
| Ищем спад | [2, 4, 7, 6, 3, 1] | 1 < 3, 3 < 6, 6 < 7 — растёт; 4 < 7 — спад, i = 1, nums[i] = 4 |
| Ищем замену | [2, 4, 7, 6, 3, 1] | справа: 1 ≤ 4, 3 ≤ 4, 6 > 4 — j = 3 |
| Обмен | [2, 6, 7, 4, 3, 1] | хвост [7, 4, 3, 1] всё ещё убывает |
| Разворот | [2, 6, 1, 3, 4, 7] | хвост стал возрастающим |
Проверим здравым смыслом: перестановки с префиксом 2, 4 закончились (хвост 7, 6, 3, 1 максимален), следующий возможный второй элемент из оставшихся {1, 3, 6, 7} больше четвёрки — шестёрка, а остальное 1, 3, 4, 7 идёт по возрастанию.
Почему это именно следующая перестановка
На собеседовании полезно уметь объяснить корректность в трёх фразах.
- Позицию
iменять обязательно, левее — незачем. Хвост правееiубывает, значит, он максимален среди своих перестановок: большей перестановки с тем же префиксомnums[0..i]нет. Зато с префиксомnums[0..i-1]она есть (в хвосте найдётся элемент большеnums[i]), и любая такая меньше любой перестановки, где изменилась позиция левееi. - На позицию
iставим наименьшее возможное большее значение. Кандидаты — элементы хвоста, большиеnums[i]. Самый правый из них — наименьший, потому что хвост убывает. - Хвост делаем минимальным. После обмена на позиции
jоказалосьnums[i], которое меньше старогоnums[j], но не меньшеnums[j + 1](иначеjбыл бы правее). Поэтому хвост остался убывающим, и разворот превращает его в возрастающий — минимальный.
Почему сравнения нестрогие
Оба цикла используют >= и <=. Именно это делает алгоритм корректным на массивах с повторами: он выдаёт только различные перестановки мультимножества. На [1, 1, 5] получается [1, 5, 1], затем [5, 1, 1], затем снова [1, 1, 5].
Если в первом цикле поставить строгое >, на [1, 2, 2] спад «найдётся» на паре равных двоек, и замены для nums[i] = 2 в хвосте не будет — второй цикл уйдёт за левую границу. Если во втором цикле поставить <, на [1, 2, 1] единица поменяется с равной ей единицей, и после разворота получится [1, 1, 2] — шаг назад вместо [2, 1, 1].
Сложность: в худшем, в среднем
Каждый из трёх проходов линейный, поэтому худший случай — : например, переход от [1, 5, 4, 3, 2] к [2, 1, 3, 4, 5] трогает весь массив. Память — .
Но длинные убывающие хвосты редки. Хвост длины не меньше — это когда последние элементов убывают, а таких перестановок доля . Математическое ожидание длины хвоста равно сумме вероятностей :
Проверим экспериментом, перебрав все перестановки подряд:
from math import factorial def average_tail(n): a = list(range(n)) total = 0 for _ in range(factorial(n)): i = n - 2 while i >= 0 and a[i] >= a[i + 1]: i -= 1 total += n - 1 - i next_permutation(a) return total / factorial(n) for n in (5, 8, 10): print(n, round(average_tail(n), 6)) # 5 1.716667 # 8 1.718279 # 10 1.718282
(Функция использует next_permutation из блока выше.) Получается : в среднем хвост короче двух элементов, и перебор всех перестановок через Next Permutation стоит шагов плюс на копирование каждой в ответ.
То же на 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]] } } const a = [1, 3, 5, 4, 2] nextPermutation(a) console.log(a) // [ 1, 4, 2, 3, 5 ]
Точка с запятой перед деструктурирующим обменом нужна, если вы пишете без точек с запятой: иначе [ склеится с предыдущей строкой.
Предыдущая перестановка
Алгоритм симметричен: меняем все сравнения на противоположные. Ищем самый правый i с nums[i] > nums[i + 1], затем самый правый j с nums[j] < nums[i] — это наибольший из меньших. Обмениваем и разворачиваем хвост, который теперь возрастал, а станет убывающим, то есть максимальным.
def prev_permutation(nums): n = len(nums) i = n - 2 while i >= 0 and nums[i] <= nums[i + 1]: i -= 1 if i >= 0: j = n - 1 while nums[j] >= nums[i]: j -= 1 nums[i], nums[j] = nums[j], nums[i] nums[i + 1:] = reversed(nums[i + 1:]) a = [2, 1, 3] prev_permutation(a) print(a) # [1, 3, 2]
Срез с reversed удобен, но создаёт копию хвоста. Если интервьюер настаивает на строгом памяти, разворачивайте двумя указателями, как в next_permutation. В C++ обе функции есть в стандартной библиотеке: std::next_permutation и std::prev_permutation, обе возвращают false, когда перешли через край.
Next Greater Element III (LeetCode 556)
Частая обёртка той же задачи: дано положительное 32-битное число, найти наименьшее большее число из тех же цифр. Если такого нет или оно не влезает в 32-битное знаковое целое, вернуть -1.
Это Next Permutation над цифрами, с двумя отличиями: последняя перестановка не «заворачивается» в первую, а даёт -1, и нужна проверка переполнения.
def next_greater_element(n): digits = list(str(n)) i = len(digits) - 2 while i >= 0 and digits[i] >= digits[i + 1]: i -= 1 if i < 0: return -1 j = len(digits) - 1 while digits[j] <= digits[i]: j -= 1 digits[i], digits[j] = digits[j], digits[i] digits[i + 1:] = reversed(digits[i + 1:]) result = int(''.join(digits)) return result if result < 2**31 else -1 print(next_greater_element(12)) # 21 print(next_greater_element(21)) # -1 print(next_greater_element(230241)) # 230412
Сравнение символов-цифр работает, потому что '0' < '1' < ... < '9'. Ведущий ноль появиться не может: первая цифра либо не меняется, либо увеличивается.
k-я перестановка (LeetCode 60)
Условие: даны и , вернуть -ю по порядку перестановку чисел в виде строки. В LeetCode , .
Вызвать next_permutation раз можно: при это максимум шагов, в среднем почти константных. Но интервьюер ждёт решение без перебора, за или лучше.
Интуиция: блоки по
Перестановки в лексикографическом порядке разбиты на блоков по первому элементу, в каждом штук. Для : первые 6 начинаются с 1, следующие 6 — с 2 и так далее. Значит, номер блока для (считая с нуля) — это , а внутри блока мы ищем перестановку с номером среди оставшихся чисел. Дальше то же самое рекурсивно.
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): index, k = divmod(k, factorial(pos - 1)) result.append(digits.pop(index)) return ''.join(result) print(get_permutation(3, 3)) # 213 print(get_permutation(4, 9)) # 2314
Главная ловушка — переход к нумерации с нуля: k -= 1 в начале. Без него даст индекс за пределами списка, а остальные ответы сдвинутся на одну перестановку.
Разбор ,
| Шаг | Свободные числа | Остаток | Блок | Индекс | Берём |
|---|---|---|---|---|---|
| 1 | 1 2 3 4 | 8 | 3! = 6 | 8 // 6 = 1 | 2 |
| 2 | 1 3 4 | 2 | 2! = 2 | 2 // 2 = 1 | 3 |
| 3 | 1 4 | 0 | 1! = 1 | 0 | 1 |
| 4 | 4 | 0 | 0! = 1 | 0 | 4 |
Ответ 2314.
Это факториальная система счисления
Индексы, которые мы получили, — 1, 1, 0, 0 — это запись числа в факториальной системе счисления: . В этой системе -й разряд справа (с нуля) имеет вес и цифру от до . Любое число от до записывается ровно одним способом, поэтому номера и перестановки соответствуют друг другу один к одному. Такую последовательность индексов называют кодом Лемера перестановки.
Перевод в факториальную систему делается как в любую другую — последовательным делением, только основание каждый раз растёт:
def to_factoradic(k, n): code = [] for radix in range(1, n + 1): k, digit = divmod(k, radix) code.append(digit) return code[::-1] print(to_factoradic(8, 4)) # [1, 1, 0, 0]
Теперь видно, почему аналогия с прибавлением единицы точна: Next Permutation — это к коду Лемера с переносами, а убывающий хвост соответствует разрядам, достигшим максимума.
Обратная задача: номер перестановки
Ранг перестановки считается в обратную сторону. Для позиции цифра кода Лемера — сколько элементов правее меньше perm[i]. Умножаем на и складываем.
from math import factorial def permutation_rank(perm): n = len(perm) rank = 0 for i in range(n): smaller = sum(1 for x in perm[i + 1:] if x < perm[i]) rank += smaller * factorial(n - 1 - i) return rank + 1 print(permutation_rank([2, 3, 1, 4])) # 9
Так перестановку можно хранить одним числом: например, состояние головоломки в BFS удобно кодировать рангом и класть в массив visited размера вместо хеш-таблицы.
Быстрее : дерево Фенвика
Узкое место обоих алгоритмов — найти «-е свободное число» (или посчитать, сколько свободных меньше данного). list.pop(index) и подсчёт в цикле дают на шаг, итого . Для это неважно, но если порядка (а дан, например, кодом Лемера), используют дерево Фенвика над флагами «число свободно»: поиск -го свободного спуском по дереву и удаление стоят .
from math import factorial def kth_permutation_fast(n, k): tree = [0] * (n + 1) # tree хранит, сколько чисел ещё свободно for i in range(1, n + 1): tree[i] += 1 parent = i + (i & -i) if parent <= n: tree[parent] += tree[i] step = 1 << n.bit_length() k -= 1 result = [] for pos in range(n - 1, -1, -1): index, k = divmod(k, factorial(pos)) # спуск по дереву: ищем (index + 1)-е свободное число node, need, bit = 0, index + 1, step while bit: nxt = node + bit if nxt <= n and tree[nxt] < need: node = nxt need -= tree[nxt] bit >>= 1 value = node + 1 result.append(value) i = value while i <= n: tree[i] -= 1 i += i & -i return result print(kth_permutation_fast(4, 9)) # [2, 3, 1, 4] print(kth_permutation_fast(10, 1000000)) # [3, 8, 9, 4, 10, 2, 6, 5, 7, 1]
Здесь factorial(pos) пересчитывается каждый раз ради краткости. Для честного нужно получать цифры кода Лемера, не вычисляя огромные факториалы, — на практике в таких задачах код Лемера и дают на входе. Это уровень олимпиадных задач, на обычном собеседовании хватает .
k-я перестановка с повторами
Если числа повторяются, блоки разного размера: число различных перестановок мультимножества с кратностями равно (подробнее — в статье про комбинаторику). Поэтому вместо деления перебираем кандидатов на текущую позицию по возрастанию и вычитаем размеры блоков, пока не попадёт внутрь.
from collections import Counter from math import factorial def count_arrangements(counter): total = factorial(sum(counter.values())) for c in counter.values(): total //= factorial(c) return total def kth_multiset(items, k): counter = Counter(items) result = [] k -= 1 for _ in range(len(items)): for x in sorted(counter): if counter[x] == 0: continue counter[x] -= 1 block = count_arrangements(counter) if k < block: result.append(x) break k -= block counter[x] += 1 return result print(kth_multiset([1, 1, 2, 2], 4)) # [2, 1, 1, 2]
Различные перестановки [1, 1, 2, 2] по порядку: 1122, 1212, 1221, 2112, … — четвёртая действительно 2112.
Типичные ошибки
- Строгие сравнения в циклах. Ломают массивы с повторами — см. раздел выше. Нужны
>=при поиске спада и<=при поиске замены. - Сортировка хвоста вместо разворота. Работает, но стоит и выдаёт непонимание: хвост уже упорядочен, достаточно развернуть.
- Поиск замены слева направо. Первый слева больший элемент хвоста — наибольший, а нужен наименьший из больших. Ищите справа или помните, что хвост убывает.
- Отдельная ветка для последней перестановки, в которой забыли развернуть массив. С
i = -1общий разворот справляется сам. - Нумерация с единицы в LeetCode 60. Забытое
k -= 1сдвигает все ответы. - В LeetCode 556 нет проверки переполнения, или «заворачивание» в минимальное число вместо
-1.
Где встречается на собеседованиях
- LeetCode 31 Next Permutation — классика уровня Medium, регулярно попадается на алгоритмических секциях. Ожидают решение и с объяснением, почему оно корректно.
- LeetCode 556 Next Greater Element III — та же задача над цифрами числа плюс переполнение.
- LeetCode 60 Permutation Sequence — факториальная система, Hard по ярлыку, но короткий код.
- LeetCode 1850 Minimum Adjacent Swaps to Reach the Kth Smallest Number — сначала раз Next Permutation, потом подсчёт соседних обменов до цели.
- Генерация всех перестановок без рекурсии — сортировка плюс Next Permutation до возврата к началу; так же получают только различные перестановки при повторах. Рекурсивные способы — в статье про перестановки и про бэктрекинг.
Хороший ход на интервью: сначала проговорить аналогию с к числу, потом четыре шага, потом пример на доске с повторяющимися элементами. Это закрывает и корректность, и граничные случаи до того, как их спросят.
Что запомнить
- Убывающий хвост максимален — меняем первый элемент перед ним.
- Меняем на наименьший больший из хвоста (самый правый подходящий), хвост разворачиваем.
- Сравнения нестрогие — тогда повторы обрабатываются сами.
- в худшем, элементов хвоста в среднем, памяти.
- -я перестановка — это в факториальной системе, ранг — обратный перевод.