Задача

6 /6


Все перестановки

Теория Нажмите, чтобы прочитать/скрыть

Перестановка длины n - это упорядоченный набор без повторений чисел 1, 2, ..., n. Например, [3, 1, 2] и [5, 4, 3, 2, 1] являются перестановками, а [1, 2, 1, 3] и [1, 2, 4] не являются.

Если задача свелась к тому, что необходимо перебрать все перестановки длины n, то можно воспользоваться удобным механизмом в С++, который называется "next_permutation".

Подробно об этом можно прочитать в документации, но смысл в том, что эта функция изменяет переданный массив на последующую перестановку в лексикографическом порядке (что в целом понятно и ее названия).

Для использования next_permutation необходимо подключить библиотеку algorithm (т.е. прописать #include <algorithm> в начале программы)

Примеры:

    vector arr;
    
    arr = { 1, 2, 3 }; // массив равен [1, 2, 3]
    
    next_permutation(arr.begin(), arr.end()); // передаем в функцию весь массив
    // теперь массив равен [1, 3, 2]


    arr = { 2, 3, 1 }; // массив равен [2, 3, 1]

    next_permutation(arr.begin(), arr.end()); // передаем в функцию весь массив
    // теперь массив равен [3, 1, 2]

    next_permutation(arr.begin() + 1, arr.begin() + 3); // можно применить функцию на части массива, но на практике такое редко требуется
    // теперь массив равен [3, 2, 1]

При этом функция имеет булево возвращаемое значение, которое равно true, если была сгенерирована следующая перестановка и false, если следующей не было (случай, когда в функцию передается максимальная перестановка в лексикографическом порядке).
Это делает возможным использование функции в цикле, что позволит нам перебирать сразу все перестановки. Из-за 0-индексации на практике зачастую удобнее работать с перестановкой чисел от 0 до n - 1, хотя формально перестановка содержит числа от 1 до n. Но к счастью это не приводит к дополнительным накладкам в коде, т.к. функция next_permutation адаптирована к 0-индексированным перестановкам (и даже к повторяющимся элементам в массиве, но подробнее вы можете выяснить самостоятельно).

В целом код перебора всех перестановок выглядит следующим образом: 
    int n; // размер перестановки
    
    vector perm(n); // perm - сокращение от "permutation", т.е. "перестановка"
    for (int i = 0; i < n; i++)
        perm[i] = i; // инициализируем начальную перестановку 0, 1, ..., n - 1

    do {
        // внутри цикла обрабатываем текущую перестановку

    } while (next_permutation(perm.begin(), perm.end())); // если не существует следующей перестановки, то закончим цикл



Данный код работает за O(n! * f(n)), где f(n) - время, за которое вы обрабатываете одну конкретную перестановку.

Задача

Вам дано натуральное число n. Выведите все перестановки размера n в лексикографическом порядке.

Входные данные:
В первой строке дано натуральное число n (1 <= n <= 7).

Выходные данные:
Выведите все перестановки по возрастанию в лексикографическом порядке. Каждую в отдельной строке. Числа в перестановке должны быть отделены пробелами.

Пример:
 
Входные данные Выходные данные
3 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1