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

Задача

Дана перестановка чисел от $1$ до $n$. Надо по ней сгенерировать следующую в лексикоргафическом порядке.

Решение

1. Пусть $i ~-$ первый элемент последовательности при проходе слева направо, начиная с которого суффикс не убывает.
2. Пусть $j ~-$ индекс минимального элемента справа от $i$, который больше $a[i]$.
3. Сделаем $swap(i, j)$, после чего суффикс, начиная с $i$ позиции отсортирован в порядке убывания.
4. Развернём суффикс, начиная с $i+1$.

Доказательство корректности

Чтобы доказать корректность, надо доказать:

1. Что получившаяся последовательность лексикографически больше исходной
2. Что не существует последовательности, которая лексикографически больше исходной, но лексикографически меньше получившейся.

---

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

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