算法1：next_permutation

#include <iostream>
#include <algorithm>

using namespace std;

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int n;

void print(int a[])
{
    for (int i = 0; i < n; i++) cout << a[i] << ' ';
    puts("");
}

int main()
{
    cin >> n;
    print(a);

    int T = 1;
    for (int i = 1; i <= n; i++) T *= i;

    while (--T)
    {
        next_permutation(a, a + n);
        print(a);
    }

    return 0;    
}

算法2：dfs()

#include <iostream>

using namespace std;

const int N = 10;

int a[N];
bool st[N];
int n;

void dfs(int u)
{
    if (u == n + 1)
    {
        for (int i = 1; i <= n; i++) cout << a[i] << ' ';
        puts("");
    }

    for (int i = 1; i <= n; i++)
    {
        if (st[i]) continue;

        st[i] = true;
        a[u] = i;
        dfs(u + 1);
        st[i] = false;
    }
}

int main()
{
    cin >> n;

    dfs(1);

    return 0;
}