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

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

Задача

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

Решение

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

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

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

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




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

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