Условие задачи
Найдите следующую перестановку. Тождественная перестановка является следующей для обратной.
Входные данные
В первой строке записано количество элементов $n$ $\left(1\leqslant n\leqslant10^5\right)$ в перестановке. Во второй строке записана перестановка из $n$ чисел.
Выходные данные
Вывести $n$ чисел — искомую перестановку.
Тесты
| № | Ввод | Вывод |
| 1 | 3 3 2 1 |
1 2 3 |
| 2 | 1 9 |
9 |
| 3 | 5 2 4 5 3 1 |
2 5 1 3 4 |
| 4 | 4 3 5 4 1 |
4 1 3 5 |
| 5 | 2 2 3 |
3 2 |
Алгоритм Нарайаны
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <iostream> #include <algorithm> using namespace std; int main() { int n; cin>>n; int a[n]; // массив для перестановки из n чисел for (int i = 0; i < n; i++) cin>> a[i]; for (int i = n - 2; i >= 0; i--) { if (a[i] < a[i+1]){ int min = i + 1; // индекс минимального элемента for (int j = i + 2; j < n; j++) { if (a[j] > a[i] && a[j] < a[min]) min = j; } swap(a[i], a[min]); reverse(&a[i+1], &a[n]); break; } if (i == 0) reverse(&a[i], &a[n]); } for (int i = 0; i < n; i++) cout << a[i] << " "; return 0; } |
Решение
Пусть $a$ — данная $n$-элементная перестановка $\left(a\;=\;\left[a_1,\;a_2,\;…,\;a_n\right]\right)$. Применяем алгоритм Нарайаны :
- Находим наибольший номер $i$ (если он существует), такой, что $a_i<a_{i+1}$. Находим такой номер $j$, что число $a_j$ является наименьшим среди чисел $a_{i+1},\;a_{i+2},\;…,\;a_n$, превосходящим $a_j$. Меняем местами элементы $a_i$ и $a_j$ .
- Если такого номера не существует, то $a$ — наибольшая $n$-элементная перестановка.
- Изменяем порядок элементов, занимающих места с $\left(i+1\right)$-го по $n$-е, на противоположный.
Полученная перестановка $\left[a_1,\;a_2,\;…,\;a_{i-1},\;a_j,\;a_n,\;a_{n-1},\;…,\;a_{j+1},\;a_i,\;a_{j-1},\;…,\;a_{i+1}\right]$ будет являться искомой перестановкой.
Ссылки
Функция next_permutation()
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; int a[n]; for (int i = 0; i < n; i++) cin >> a[i]; next_permutation(a, a+n); for (int i = 0; i < n; i++) cout << a[i] << " "; return 0; } |
Решение
Применяем функцию next_permutation() , которая генерирует следующую лексиграфическую перестановку в диапазоне элементов.