Построение следующей в лексикографическом порядке перестановки по данной: различия между версиями
Материал из Algocode wiki
Строка 1: | Строка 1: | ||
= Задача = | = Задача = | ||
− | Дана перестановка чисел от $1$ до $n$. Надо по ней сгенерировать следующую в | + | Дана перестановка чисел от $1$ до $n$. Надо по ней сгенерировать следующую в лексикографическом порядке. |
= Решение = | = Решение = | ||
− | # Пусть $i ~-$ первый элемент последовательности при проходе | + | # Пусть $i ~-$ первый элемент последовательности при проходе справа налево, для которого $a[i] \leqslant a[i + 1]$. |
# Пусть $j ~-$ индекс минимального элемента справа от $i$, который больше $a[i]$. | # Пусть $j ~-$ индекс минимального элемента справа от $i$, который больше $a[i]$. | ||
# Сделаем $swap(i, j)$, после чего суффикс, начиная с $i$ позиции отсортирован в порядке убывания. | # Сделаем $swap(i, j)$, после чего суффикс, начиная с $i$ позиции отсортирован в порядке убывания. |
Текущая версия на 13:53, 7 февраля 2021
Задача
Дана перестановка чисел от $1$ до $n$. Надо по ней сгенерировать следующую в лексикографическом порядке.
Решение
- Пусть $i ~-$ первый элемент последовательности при проходе справа налево, для которого $a[i] \leqslant a[i + 1]$.
- Пусть $j ~-$ индекс минимального элемента справа от $i$, который больше $a[i]$.
- Сделаем $swap(i, j)$, после чего суффикс, начиная с $i$ позиции отсортирован в порядке убывания.
- Развернём суффикс, начиная с $i+1$.
Доказательство корректности
Чтобы доказать корректность, надо доказать:
- Что получившаяся последовательность лексикографически больше исходной
- Что не существует последовательности, которая лексикографически больше исходной, но лексикографически меньше получившейся.
Автор конспекта: Александр Гришутин
По всем вопросам пишите в telegram @rationalex