2386. Следующая перестановка

Найдите следующую перестановку. Считайте, что за перестановкой (n, n – 1, ..., 2, 1) следует тождественная перестановка (1, 2, ..., n – 1, n).

Вход. Первая строка содержит количество элементов n (1 ≤ n ≤ 10⁵) в перестановке. Вторая строка содержит перестановку из n чисел.

Выход. Выведите n чисел – следующую перестановку для заданной.

Пример входа	Пример выхода
3 3 2 1	1 2 3

РЕШЕНИЕ

комбинаторика

Анализ алгоритма

Для генерации следующей перестановки воспользуемся функцией next_permutation. Для лексикографически наибольшей перестановки (n, n – 1, n – 2, …, 2, 1) следующей считается лексикографически наименьшая (1, 2, …, n – 2, n – 1, n).

Опишем алгоритм нахождения лексикографически следующей перестановки. Перестановка P = (p₁, p₂, …, p_n) меньше Q = (q₁, q₂, …, q_n), если существует такой индекс i, что p_i < q_i, и при этом p_j = q_j для всех j < i. Например

(3, 5, 4, 6, 7) < (3, 5, 6, 4, 7)

Покажем на примере, как найти перестановку, следующую за

P = (5, 6, 7, 4, 3)

Просматриваем текущую перестановку справа налево, пока следующее число больше предыдущего. Останавливаемся, когда правило нарушится. Место остановки подчеркнем: (5, 6, 7, 4, 3). Снова просматриваем пройденный путь (справа налево) до тех пор, пока не дойдем до первого числа, которое больше отмеченного. Место второй остановки отметим двойным подчеркиванием: (5, 6, 7, 4, 3). Поменяем местами отмеченные числа: (5, 7, 6, 4, 3). Теперь все числа, расположенные справа от двойного подчеркивания, упорядочим в порядке возрастания. Поскольку они до этих пор были упорядочены в убывающем порядке, то достаточно перевернуть указанный отрезок. Получим Q = (5, 7, 3, 4, 6). Это и есть перестановка, непосредственно следующая за P.

Пример

Найдем перестановку, следующую за P = (7, 5, 3, 6, 4, 2, 1).

Реализация алгоритма

Объявим массив для генерации перестановок.

int m[MAX];

Читаем входные данные.

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

Генерируем следующую перестановку при помощи функции next_permutation. Если текущей является лексикографически наибольшая перестановка, то после вызова функции next_permutation массив m примет вид (1, 2, …, n – 1, n).

next_permutation(m,m+n);

Выводим искомую следующую перестановку.

for(i = 0; i < n; i++)

printf("%d ",m[i]);

printf("\n");