Следующая перестановка: алгоритм Нараяны и k-я перестановка

LeetCode 31 Next Permutation за O(n) на месте: алгоритм Нараяны с доказательством, предыдущая перестановка, k-я перестановка (LeetCode 60) и ранг через факториальную систему.

10 мин чтенияалгоритмы · комбинаторика · массивы · python

Коротко

ВопросОтвет
Что делает Next PermutationПереставляет массив в следующую по лексикографическому порядку перестановку, а последнюю — в первую
АлгоритмНайти справа первый спад nums[i] < nums[i+1], обменять nums[i] с ближайшим большим справа, развернуть хвост
СложностьO(n)O(n) в худшем случае, в среднем O(1)O(1) на шаг, память O(1)O(1)
k-я перестановка (LC 60)Записать k−1k - 1 в факториальной системе счисления: цифры — индексы среди ещё не взятых чисел
Обратная задачаРанг перестановки: сколько меньших чисел стоит правее каждой позиции, умножить на факториалы

В статье про перестановки Next Permutation — один из разделов среди бэктрекинга и обработки дубликатов. Здесь разберём только порядок перестановок: почему алгоритм даёт именно следующую перестановку, как его развернуть в обратную сторону, почему шаг в среднем стоит константу и как прыгнуть сразу к kk-й перестановке или, наоборот, узнать номер данной.

Лексикографический порядок и аналогия со счётчиком

Перестановки сравниваются как слова в словаре: по первому различающемуся элементу. Для [1, 2, 3] порядок такой:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

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

Лучшая интуиция — прибавление единицы к числу. После 1299 идёт 1300: девятки в хвосте уже максимальны, увеличить их нельзя, поэтому растёт первая цифра левее них, а хвост сбрасывается в минимум — нули. Если вы решали задачу Plus One, это ровно её логика с переносом.

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

Наивное решение

Сгенерировать все перестановки, отсортировать, найти текущую и взять следующую. Это O(n⋅n!)O(n \cdot n!) времени и столько же памяти. Уже при n=12n = 12 перестановок почти полмиллиарда, при n=20n = 20 — больше 2⋅10182 \cdot 10^{18}. На собеседовании такой вариант стоит только назвать, чтобы показать, от чего отталкиваетесь.

Алгоритм Нараяны

Алгоритм известен давно: Дональд Кнут в «Искусстве программирования» (том 4A, раздел о генерации перестановок) возводит его к индийскому математику Нараяне Пандиту, XIV век. В русскоязычной литературе его так и называют — алгоритм Нараяны. Шаги:

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

Сложность: O(n)O(n) в худшем, O(1)O(1) в среднем

Каждый из трёх проходов линейный, поэтому худший случай — O(n)O(n): например, переход от [1, 5, 4, 3, 2] к [2, 1, 3, 4, 5] трогает весь массив. Память — O(1)O(1).

Но длинные убывающие хвосты редки. Хвост длины не меньше mm — это когда последние mm элементов убывают, а таких перестановок доля 1/m!1/m!. Математическое ожидание длины хвоста LL равно сумме вероятностей P(L≥m)P(L \ge m):

E[L]=∑m=1n1m!→e−1≈1.718.\mathbb{E}[L] = \sum_{m = 1}^{n} \frac{1}{m!} \to e - 1 \approx 1.718.

Проверим экспериментом, перебрав все перестановки подряд:

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 из блока выше.) Получается e−1e - 1: в среднем хвост короче двух элементов, и перебор всех перестановок через Next Permutation стоит O(n!)O(n!) шагов плюс O(n)O(n) на копирование каждой в ответ.

То же на 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 удобен, но создаёт копию хвоста. Если интервьюер настаивает на строгом O(1)O(1) памяти, разворачивайте двумя указателями, как в 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)

Условие: даны nn и kk, вернуть kk-ю по порядку перестановку чисел 1..n1..n в виде строки. В LeetCode 1≤n≤91 \le n \le 9, 1≤k≤n!1 \le k \le n!.

Вызвать next_permutation k−1k - 1 раз можно: при n=9n = 9 это максимум 362 879362\,879 шагов, в среднем почти константных. Но интервьюер ждёт решение без перебора, за O(n2)O(n^2) или лучше.

Интуиция: блоки по (n−1)!(n-1)!

Перестановки 1..n1..n в лексикографическом порядке разбиты на nn блоков по первому элементу, в каждом (n−1)!(n-1)! штук. Для n=4n = 4: первые 6 начинаются с 1, следующие 6 — с 2 и так далее. Значит, номер блока для kk (считая с нуля) — это ⌊(k−1)/(n−1)!⌋\lfloor (k-1) / (n-1)! \rfloor, а внутри блока мы ищем перестановку с номером (k−1) mod (n−1)!(k - 1) \bmod (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): 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 в начале. Без него k=n!k = n! даст индекс за пределами списка, а остальные ответы сдвинутся на одну перестановку.

Разбор n=4n = 4, k=9k = 9

ШагСвободные числаОстаток kkБлокИндексБерём
11 2 3 483! = 68 // 6 = 12
21 3 422! = 22 // 2 = 13
31 401! = 101
4400! = 104

Ответ 2314.

Это факториальная система счисления

Индексы, которые мы получили, — 1, 1, 0, 0 — это запись числа k−1=8k - 1 = 8 в факториальной системе счисления: 8=1⋅3!+1⋅2!+0⋅1!+0⋅0!8 = 1 \cdot 3! + 1 \cdot 2! + 0 \cdot 1! + 0 \cdot 0!. В этой системе ii-й разряд справа (с нуля) имеет вес i!i! и цифру от 00 до ii. Любое число от 00 до n!−1n! - 1 записывается ровно одним способом, поэтому номера и перестановки соответствуют друг другу один к одному. Такую последовательность индексов называют кодом Лемера перестановки.

Перевод в факториальную систему делается как в любую другую — последовательным делением, только основание каждый раз растёт:

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 — это +1+1 к коду Лемера с переносами, а убывающий хвост соответствует разрядам, достигшим максимума.

Обратная задача: номер перестановки

Ранг перестановки считается в обратную сторону. Для позиции ii цифра кода Лемера — сколько элементов правее ii меньше perm[i]. Умножаем на (n−1−i)!(n - 1 - 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 размера n!n! вместо хеш-таблицы.

Быстрее O(n2)O(n^2): дерево Фенвика

Узкое место обоих алгоритмов — найти «tt-е свободное число» (или посчитать, сколько свободных меньше данного). list.pop(index) и подсчёт в цикле дают O(n)O(n) на шаг, итого O(n2)O(n^2). Для n≤9n \le 9 это неважно, но если nn порядка 10510^5 (а kk дан, например, кодом Лемера), используют дерево Фенвика над флагами «число свободно»: поиск tt-го свободного спуском по дереву и удаление стоят O(log⁡n)O(\log n).

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) пересчитывается каждый раз ради краткости. Для честного O(nlog⁡n)O(n \log n) нужно получать цифры кода Лемера, не вычисляя огромные факториалы, — на практике в таких задачах код Лемера и дают на входе. Это уровень олимпиадных задач, на обычном собеседовании хватает O(n2)O(n^2).

k-я перестановка с повторами

Если числа повторяются, блоки разного размера: число различных перестановок мультимножества с кратностями c1,c2,…c_1, c_2, \ldots равно m!c1! c2!⋯\dfrac{m!}{c_1! \, c_2! \cdots} (подробнее — в статье про комбинаторику). Поэтому вместо деления перебираем кандидатов на текущую позицию по возрастанию и вычитаем размеры блоков, пока kk не попадёт внутрь.

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.

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

  • Строгие сравнения в циклах. Ломают массивы с повторами — см. раздел выше. Нужны >= при поиске спада и <= при поиске замены.
  • Сортировка хвоста вместо разворота. Работает, но стоит O(nlog⁡n)O(n \log n) и выдаёт непонимание: хвост уже упорядочен, достаточно развернуть.
  • Поиск замены слева направо. Первый слева больший элемент хвоста — наибольший, а нужен наименьший из больших. Ищите справа или помните, что хвост убывает.
  • Отдельная ветка для последней перестановки, в которой забыли развернуть массив. С i = -1 общий разворот справляется сам.
  • Нумерация с единицы в LeetCode 60. Забытое k -= 1 сдвигает все ответы.
  • В LeetCode 556 нет проверки переполнения, или «заворачивание» в минимальное число вместо -1.

Где встречается на собеседованиях

  • LeetCode 31 Next Permutation — классика уровня Medium, регулярно попадается на алгоритмических секциях. Ожидают решение O(n)O(n) и O(1)O(1) с объяснением, почему оно корректно.
  • LeetCode 556 Next Greater Element III — та же задача над цифрами числа плюс переполнение.
  • LeetCode 60 Permutation Sequence — факториальная система, Hard по ярлыку, но короткий код.
  • LeetCode 1850 Minimum Adjacent Swaps to Reach the Kth Smallest Number — сначала kk раз Next Permutation, потом подсчёт соседних обменов до цели.
  • Генерация всех перестановок без рекурсии — сортировка плюс Next Permutation до возврата к началу; так же получают только различные перестановки при повторах. Рекурсивные способы — в статье про перестановки и про бэктрекинг.

Хороший ход на интервью: сначала проговорить аналогию с +1+1 к числу, потом четыре шага, потом пример на доске с повторяющимися элементами. Это закрывает и корректность, и граничные случаи до того, как их спросят.

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

  1. Убывающий хвост максимален — меняем первый элемент перед ним.
  2. Меняем на наименьший больший из хвоста (самый правый подходящий), хвост разворачиваем.
  3. Сравнения нестрогие — тогда повторы обрабатываются сами.
  4. O(n)O(n) в худшем, e−1e - 1 элементов хвоста в среднем, O(1)O(1) памяти.
  5. kk-я перестановка — это k−1k - 1 в факториальной системе, ранг — обратный перевод.

Потренироваться в спокойной обстановке

Все задачи