Основные элементы комбинаторики Комбинаторика

#include using namespace std; int n; int a[100000]; bool used[100000]; vector v; void f(int k) { //k - количество уже использованных индексов if (k == n) { cout << "Permutation: "; for (int i: v) { cout << i << ", "; } cout << endl; return; } for (int i = 0; i < n; i++) { if (!used[i]) { used[i] = true; //Добавляем в текущую перестановку элемент a[i] v.push_back(i); f(k + 1); //Рекурсивно перебираем все перестановки, продолжающиеся a[i] v.pop_back(); used[i] = false; //Убираем из текущей перестановки элемент a[i] } } } int main() { cin >> n; for (int i = 0; i < n; i++) { a[i] = i + 1; } f(0); }

Сложность этого алгоритма порядка O(N!∗N2)O(N!∗N2), он будет укладываться в ограничение по времени при N≤10N≤10.
Стоит отметить, что этот алгоритм выводит перестановки в лексикографическом порядке. Так же, как расположены слова в словаре.
Приём рекурсивного перебора, использующийся в этом алгоритме, очень часто может добавить вам 15-20 баллов по задаче, по которой иначе вы бы получили 0 (речь идёт о белорусской системе оценки, где каждый тест оценивается индивидуально). Внимательно изучите его и поэкспериментируйте с ним.
Впрочем стандартная библиотека C++ содержит функции, позволяющие вам перебирать перестановки последовательности в лексикографическом порядке без написания своего кода:
//Преобразует перестановку в следующую лексикографически
//Если перестановка уже является максимальной, возвращает false