题目描述

把 $1~n$ 这 $n$ 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式
一个整数$n$。

输出格式
按照从小到大的顺序输出所有方案，每行1个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围
$1 \le n \le 9$
输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

算法1

STL做法(特殊做法)

C++STL中全排列函数next_permutation，详情可以自己百度

正解

(暴力枚举)

首先提一句，代码风格诡异，代码量大，而且巨丑

我的思路大致是这样的，首先呢我们知道，这道题目的输出是按照字典序的，所以呢我们果断选择深度优先搜索

接着来看，我们的循环就不能是之前类似于for(int i=x+1;i<=n;i)了，就必须是for (i=1;i<=n;i0)，因为此时我们不再是之前的升序排序输出！

所以说这里必须引用搜索中极为常见的vis数组，也就是判重数组，判断数组，判断这个数字是否被使用过。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,vis[11];
stack<int> p;
void dfs(int x)
{
    if (x==n+1)
    {
        stack<int> q=p,s;
        while(!p.empty())
            s.push(p.top()),p.pop();
        while(!s.empty())
            cout<<s.top()<<" ",s.pop();
        p=q;
        cout<<endl;
        return ;
    }
    for (int i=1;i<=n;i++)
        if (!vis[i])
        {
            vis[i]=1;
            p.push(i);
            dfs(x+1);
            vis[i]=0;
            p.pop();
        }
    return ;
}
int main()
{
    cin>>n;
    dfs(1);
}

正解2

#include <bits/stdc++.h>
using namespace std;
int q[110],n,vis[110];
void dfs(int x)
{
    if (q[0]==n)
    {
        for (int i=1;i<=q[0];i++)
            cout<<q[i]<<" ";
        puts("");
        return ;
    }
    for (int i=1;i<=n;i++)
        if (!vis[i])
        {
            vis[i]=1;
            q[++q[0]]=i;
            dfs(i+1);
            q[q[0]--]=0;
            vis[i]=0;
        }
    return ;
}
int main()
{
    cin>>n;
    dfs(1);
}

正解三 位运算

#include <bits/stdc++.h>
using namespace std;
int q[110],n;
void dfs(int x,int now)
{
    if (q[0]==n)
    {
        for (int i=1;i<=q[0];i++)
            cout<<q[i]<<" ";
        puts("");
        return ;
    }
    for (int i=1;i<=n;i++)
        if (!(now>>(i-1) & 1))
        {
            q[++q[0]]=i;
            dfs(i+1,now+(1<<(i-1)));
            q[q[0]--]=0;
        }
    return ;
}
int main()
{
    cin>>n;
    dfs(1,0);
}

非递归类型枚举.

#include <bits/stdc++.h>
using namespace std;
const int N=11;
int n,a[N];
int main() 
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        a[i]=i;
    do
    {
        for(int i=1;i<=n;i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }while(next_permutation(a+1,a+1+n));
    return 0;
}