Поиск k-ой в лексикографическом порядке перестановки: различия между версиями
| Строка 1: | Строка 1: | ||
= Задача = | = Задача = | ||
| − | Даны натуральные числа $k$ и $n s.t. 0 \leq k < n!$. Надо найти $k$-ую в лексикографическом порядке перестановку чисел от $1$ до $n$. Например, для $n = 3$ и $k = 4$ надо вывести $3 1 2$. | + | Даны натуральные числа $k$ и $n$ $s.t. 0 \leq k < n!$. Надо найти $k$-ую в лексикографическом порядке перестановку чисел от $1$ до $n$. Например, для $n = 3$ и $k = 4$ надо вывести $3 1 2$. |
= Решение = | = Решение = | ||
| − | Вспомним, что если перестановка $k$-ая в лексикографическом порядке, то существует ровно $k$ перестановок, которые меньше неё | + | Вспомним, что если перестановка $k$-ая в лексикографическом порядке, то существует ровно $k$ перестановок, которые меньше неё. Будем находить элементы искомой позиции по очереди слева направо, постепенно набирая (неявно) те самые $k$ перестановок, которые меньше нас. |
| − | Если мы поставим на первое место не $1$, а $2$, то мы заведомо получим перестановку, которая больше всех перестановок, которые начинаются на $1$, а их $(n-1)!$. Если мы поставим на первое место не $2$, а $3$, то перестановок, которые меньше нас уже $2 \cdot (n-1)!$ итд. Значит, давайте увеличивать первую цифру до тех пор, пока можем (пока $(d-1) \cdot (n-1)! \leq k)$. Затем вычтем из $k$ то число перестановок, которых мы уже заведомо лексикографически больше, и начнём перебирать вторую цифру, теперь уже вычитая $(n-2)!$, пока можно. | + | Если мы поставим на первое место не $1$, а $2$, то мы заведомо получим перестановку, которая больше всех перестановок, которые начинаются на $1$, а их $(n-1)!$. Если мы поставим на первое место не $2$, а $3$, то перестановок, которые меньше нас уже $2 \cdot (n-1)!$ итд. Значит, давайте увеличивать первую цифру до тех пор, пока можем (пока $(d-1) \cdot (n-1)! \leq k)$. Затем вычтем из $k$ то число перестановок, которых мы уже заведомо лексикографически больше, и начнём перебирать вторую цифру, теперь уже вычитая $(n-2)!$, пока можно. Разумеется, каждый раз перебирая цифру на очередную позицию, мы будем пропускать цифры, которые мы уже поставили ранее. |
= Корректность = | = Корректность = | ||
Версия 10:37, 29 февраля 2020
Задача
Даны натуральные числа $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