Перестановка длины 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) - время, за которое вы обрабатываете одну конкретную перестановку.