算法1

#include<iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int q[N];

int main(){
    cin>>n;
    for(int i = 0; i < n; i++) q[i] = i + 1;
    do{
        for(int i = 0; i < n; i++) cout<<q[i]<<" ";
        cout<<endl;
    }while(next_permutation(q,q+n));
    return 0;
}

算法2 递归

#include<iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int q[N],path[N];
bool st[N];

void dfs(int k){
    if(k == n){
        for(int i = 0; i < n; i++) cout<<path[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i = 0; i < n; i++){
        if(!st[i]){
            st[i] = true;
            path[k] = q[i];
            dfs(k + 1);
            st[i] = false;
        }
    }
}

int main(){
    cin>>n;
    for(int i = 0; i < n; i++) q[i] = i + 1;
    dfs(0);
    return 0;
}

算法3 手动实现next_permutation

#include<iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    int n;
    int q[15];

    cin>>n;
    for(int i = 0; i < n; i++) q[i] = i + 1;
    while(true){
        for(int i = 0; i < n; i++) cout<<q[i]<<" ";
        cout<<endl;

        int k = n - 1;
        while(q[k - 1] > q[k]) k--;
        if(k == 0) break;
        k--;
        int t = k;
        while(t + 1 < n && q[t + 1] > q[k]) t++;
        swap(q[t],q[k]);
        reverse(q + k + 1,q + n);
    }
    return 0;
}