Поиск k-ой в лексикографическом порядке перестановки

Материал из Algocode wiki
Версия от 00:24, 9 мая 2020; Rationalex (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

Даны натуральные числа $k$ и $n$ $s.t. 0 \leq k < n!$. Надо найти $k$-ую в лексикографическом порядке перестановку чисел от $1$ до $n$. Например, для $n = 3$ и $k = 4$ надо вывести $3 1 2$.

Решение

Вспомним, что если перестановка $k$-ая в лексикографическом порядке, то существует ровно $k$ перестановок, которые меньше неё. Будем находить элементы искомой позиции по очереди слева направо, постепенно набирая (неявно) те самые $k$ перестановок, которые меньше нас.

Если мы поставим на первое место не $1$, а $2$, то мы заведомо получим перестановку, которая больше всех перестановок, которые начинаются на $1$, а их $(n-1)!$. Если мы поставим на первое место не $2$, а $3$, то перестановок, которые меньше нас уже $2 \cdot (n-1)!$ итд. Значит, давайте увеличивать первую цифру до тех пор, пока можем (пока $(d-1) \cdot (n-1)! \leq k)$. Затем вычтем из $k$ то число перестановок, которых мы уже заведомо лексикографически больше, и начнём перебирать вторую цифру, теперь уже вычитая $(n-2)!$, пока можно. Разумеется, каждый раз перебирая цифру на очередную позицию, мы будем пропускать цифры, которые мы уже поставили ранее.

Корректность

Посколько классы перестановок, которые мы вычитаем, не пересекаются, то в конце мы получим перестановку $\sigma$, для которой существует ровно $k$ перестановок, которые лексикографически меньше $\sigma$.



Автор конспекта: Александр Гришутин

По всем вопросам пишите в telegram @rationalex