需求问题

输入一个数 n , 输出 1~n 的全排列。

故事情节

这里我们先将这个问题形象化， 举个例子，假如有编号为 1 、2、3 的 3 张扑克牌和编号为 1 、2、3 的3 个盒子。现在需要将这 3 张扑克牌分别放到 3 个盒子里面， 并且每个盒子有且只能放一张扑克牌。那么一共有多少种不同的放法呢？

好了， 现在轮到小哼出马。小哼手拿 3 张扑克牌， 首先走到了 1 号盒子面前。此时小哼心里想； 我是先放1号扑克牌， 还是先放2号扑克牌， 还是先放3号扑克牌呢？ 现在要生成的是全排列， 很显然这三种情况都需要去尝试。小哼说那我们约定一个顺序吧： 每次到一个盒子面前时， 都先放1号， 再放2号， 最后放3号扑克牌。说完小哼走到了1号盒子前， 将1号扑克牌放到第1个盒子中。

放好之后小哼往后走一步， 来到了2号盒子面前。本来按照之前约定的规则， 每到一个新的盒子面前， 要按照1号、2号、3号扑克牌的顺序来放。但是现在小哼手中只剩下2号和3号扑克牌了，于是小哼将2号扑克牌放入了2号盒子中。放好之后小哼再往后走一步，来到了3号盒子面前。

现在小哼已经来到了3号盒子面前，按照之前约定的顺序，还是应该按照1号、2号、3号扑克牌的顺序来放， 但是小哼手中只有3号扑克牌了， 于是只能往3号盒子里面放3号扑克牌。放好后， 小哼再往后走一步， 来到了4号盒子面前。咦！ 没有第4个盒子， 其实我们并不需要第4个盒子， 因为手中的扑克牌已经放完了。

我们发现当小哼走到第4个盒子的时候， 已经完成了一种排列， 这个排列就是前面3个盒子中的扑克牌号码， 即“ 1 2 3 ”。

是不是到此就结束了呢？ 肯定没有！ 产生了一种排列之后小哼需要立即返回。现在小哼需要退一步重新回到3号盒子面前。

好！ 现在小哼已经回到了3号盒子面前，需要取回之前放在3号盒子中的扑克牌， 再去尝试看看还能否放别的扑克牌， 从而产生一个新的排列。于是小哼取回了3号扑克牌。当小哼再想往3号盒子放别的扑克牌的时候， 却发现手中仍然只有3号扑克牌， 没有别的选择。于是小哼不得不再往回退一步， 回到2号盒子面前。

小哼回到2号盒子后， 收回了2号扑克牌。现在小哼手里面有两张扑克牌了， 分别是2号和3号扑克牌。按照之前约定的顺序， 现在需要往2号盒子中放3号扑克牌（ 上一次放的是2号扑克牌） 。放好之后小哼又向后走一步， 再次来到了3号盒子面前。

小哼再次来到3号盒子后， 将手中仅剩的2 号扑克牌放入了3 号盒子。又来到4号盒子面前。当然了， 这里并没有4号盒子。此时又产生了一个新的排列 “1 3 2”。

接下来按照刚才的步骤去模拟， 便会依次生成所有排列。

说了半天， 这么复杂的过程如何用程序实现呢？ 我们现在来解决最基本的问题： 如何往小盒子中放扑克牌。每一个小盒子都可能放1号、2号或者3号扑克牌， 这需要一一去尝试，这里一个for循环就可以解决。

for (i=1; i<=n; i++)
{
    a[step] = i;    //将i号扑克牌放入到第step个盒子中
}

这里数组a是用来表示小盒子的， 变量step表示当前正处在第step个小盒子面前。a[step]=i就是将第i 号扑克牌放入到第step个盒子中。这里有一个问题那就是， 如果一张扑克牌已经放到别的小盒子中了， 那么此时就不能再放入同样的扑克牌到当前小盒子中， 因为此时手中已经没有这张扑克牌了。因此还需要一个数组vis来标记哪些牌已经使用了。

for(int i=1; i<=n; i++) {
    if(vis[i] == 0) {//将vis[i]等于0表示i号扑克牌还在手上
        a[step] = i;//将i号扑克牌放到第step个盒子中
        vis[i] = 1;//将vis[i]设为1，表示i这张牌已经不在手上
    }
}

OK, 现在已经处理完第step个小盒子了， 接下来需要往下走一步， 继续处理第step+1个小盒子。那么如何处理第step+1个小盒子呢？ 处理方法其实和我们刚刚处理第step个小盒子的方法是相同的。因此就很容易想到（ 如果这个词伤害了您， 我表示深深的歉意＾＿＾），把刚才的处理第step个小盒子的代码封装为一个函数， 我们为这个函数起个名字， 就叫做dfs吧， 如下。

void dfs(int step) //step表示现在站在第几个盒子面前
{
    for(int i=1; i<=n; i++){
        //判断扑克牌i是否还在手上
        if(vis[i] == 0) {//将vis[i]等于0表示i号扑克牌还在手上
            a[step] = i;//将i号扑克牌放到第step个盒子中
            vis[i] = 1;//将vis[i]设为1，表示i这张牌已经不在手上
        }
    }
}

把这个过程写成函数后， 刚才的问题就好办了。在处理完第step个小盒子之后， 紧接着处理第step+1个小盒子， 处理第step+1和小盒子的方法就是dfs(step+1)， 请注意下面代码中加粗的语句。

void dfs(int step) //step表示现在站在第几个盒子面前
{
    for(int i=1; i<=n; i++){
        //判断扑克牌i是否还在手上
        if(vis[i] == 0) {//将vis[i]等于0表示i号扑克牌还在手上
            a[step] = i;//将i号扑克牌放到第step个盒子中
            vis[i] = 1;//将vis[i]设为1，表示i这张牌已经不在手上
            dfs(step+1);//通过函数的递归调用来实现（自己调用自己）
            vis[i] = 0;//这一步非常重要，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
        }
    }
}

上面代码中的vis[i]=0这条语句非常重要， 这句话的作用是将小盒子中的扑克牌收回，因为在一次摆放尝试结束返回的时候， 如果不把刚才放入小盒子中的扑克牌收回， 那将无法再进行下一次摆放。还剩下一个问题， 就是什么时候该输出一个满足要求的序列呢。其实当我们处理到第n+1个小盒子的时候（ 即step等于n+1) ， 那么说明n个盒子都已经放好扑克牌了， 这里就将1~n个小盒子中的扑克牌编号打印出来就可以了， 如下。注意！ 打印完毕一定要立即return, 不然这个程序就会永无止境地运行下去了， 想一想为什么吧。

void dfs(int step) //step表示现在站在第几个盒子面前
{
    if(step == n+1) //如果站在第n+1个盒子面前，则表示前n个盒子已经放好扑克牌
    {
        //输出一种全排列
        for(int i=1; i<=n; i++){
            cout << a[i] << ' ';
        }
        cout << endl;
        return ;//返回之前的一步
    }
    for(int i=1; i<=n; i++){
        //判断扑克牌i是否还在手上
        if(vis[i] == 0) {//将vis[i]等于0表示i号扑克牌还在手上
            a[step] = i;//将i号扑克牌放到第step个盒子中
            vis[i] = 1;//将vis[i]设为1，表示i这张牌已经不在手上
            dfs(step+1);//通过函数的递归调用来实现（自己调用自己）
            vis[i] = 0;//这一步非常重要，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
        }
    }
}

深度优先搜索DFS模板

int dfs(int step)
{
    if(满足输出条件)
    {
        输出解;
        return ;
    }

    for(int i=1;i<=尝试方法数;i++)
        if(满足进一步搜索条件)
        {
            为进一步搜索所需要的状态打上标记;
            dfs(step+1);
            恢复到打标记前的状态;//也就是说的'回溯一步'
        }

}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com