Генерация всех перестановок

n = int(input())
used = [0] * (n + 1)
Alf = list(range(1, n + 1))

def gen(p, n):
    if len(p) == n:
        print(*p)
        return
    for c in Alf:
        p.append(c)
        if not used[c]:
            used[c] = 1
            gen(p, n)
            used[c] = 0
        p.pop()

p = []
gen(p, n)

#include <bits/stdc++.h>
using namespace std;

vector<int> used;
vector<int> Alf;
vector<int> p;

void gen(vector<int>& p, int n) {
    if (p.size() == n) {
        for (int x : p) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int c : Alf) {
        p.push_back(c);
        if (!used[c]) {
            used[c] = 1;
            gen(p, n);
            used[c] = 0;
        }
        p.pop_back();
    }
}

int main() {
    int n;
    cin >> n;
    used.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        Alf.push_back(i);
    }
    gen(p, n);
    return 0;
}