第八节 从全排列到深度优先搜索算法

全排列

  什么是全排列？就是一组数据所有可能的排列顺序。如果使用暴力枚举的方法，需要对每一个位置都进行一次循环，如果有n个数据则需要循环n次，而且还要加上对重复序列的判断。

  可喜的是，在STL中有两个函数可以帮我们实现字典序的全排列。他们分别是：next_permutation()prev_permutation()，参数是数据的开始和结束地址。举个例子，比如一个字符数组：a,b,c，它的下一个序列就是a,c,b。在处理全排列问题的时候，使用比较方便。这两个函数在算法头文件中。

  由于这两个函数是根据字典序来给出下一个全排列，如果想要得出所有的全排列，则需要首先对序列进行排序。

  蓝桥杯中很多题目可以使用这种方法来解决，以第七届蓝桥杯的第三题为例：

　　B　　 DEF
A + —— + ——— = 10
　　C　　 GHI
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：
6+8/3+952/714 就是一种解法，
5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。

  代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){

    int a[10];
    int i;
    int sum[4];
    int ans;

    for(i=1;i<=9;++i){
        a[i]=i;
    }

    ans=0;
    do{
        sum[0]=a[1]*a[3]*(a[7]*100+a[8]*10+a[9]);
        sum[1]=a[2]*(a[7]*100+a[8]*10+a[9]);
        sum[2]=(a[4]*100+a[5]*10+a[6])*a[3];
        sum[3]=10*a[3]*(a[7]*100+a[8]*10+a[9]);

        if(sum[0]+sum[1]+sum[2]==sum[3]){
            ++ans;
        }
    }while(next_permutation(a+1,a+1+9));
    printf("%d\n",ans);
    return 0;
}

深度优先搜索dfs算法

  突然想要感叹一句：终于要讲到dfs算法了。为什么要发出这样的感叹呢，因为从这里开始，我们真正要接触到算法的内容了。之前的学习都可以说是小打小闹，到这里再是正主。

  事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。dfs算法是算法学习过程中的重中之重，因为全排列是个一维的过程，为了便于大家的理解，我就从它开始吧。

  有a、b、c三个盒子，以及1，2，3三只球。我们将球放到盒子里，每个盒子只能放一个球，求一共有几种放法。如果形象地形容这个全排列的过程，将会是这个样子：首先按照字典序顺序放球，也就是在a盒子中放1号球，b盒子中放2号球，c盒子中放3号球。再向后走就没有盒子了，同时我们手中也没有剩余球了。这个时候，往回走，寻找有没有其他的放球顺序。先回到c盒子前拿出3号球，再到b盒子前拿出2号球。这时候，又产生了一种排列方式：把3号球放到b盒子中，2号球放到c盒子中。接下来以此类推，产生剩余的序列。

  那么，我们把上面的过程用程序来模拟一下。首先是第一种放置方法，先按照升序将球放好：

1
2
3
for(int i=1;i<=n;i++) {
    a[step] = i;
}

  这里的数组a表示盒子的序列，变量step表示我们正处在第step个盒子的前面。a[step]=i的意思就是将第i个球放到第step个盒子里。但是需要注意的是，球一旦放进一个盒子里，就不能放在另一个盒子里了。这时候，我们需要记录一下。

1
2
3
4
5
6
for(int i;i<=n;i++) {
    if(book[i]==0) { //book[i]==0表示球还在我们手上
        a[step]=i;
        book[i]=1;   //标记i号球已经放到盒子里了
    }
}

  那么，我们既然在第step个盒子里放球了，后面就要继续向后放了。很明显，这是一个递归的过程。我们将要写的过程封装到函数里，将这个函数命名为dfs。然后在里面处理第step+1个盒子。

1
2
3
4
5
6
7
8
9
10
void dfs(int step) {
    for(int i;i<=n;i++) {
        if(book[i]==0) { 
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
}

  细心的同学可能已经注意到了，除了除以step+1个盒子之外，我们还另外加了一行代码book[i]=0，为什么要加上这一句呢？我们想一下，递归放完所有的球之后，我们是不是在回来的过程中要将这个球从盒子里拿出来呀。如果没有这个操作，这将会对接下来的放置造成障碍。

  在之前的学习中，我们都知道，递归必须要有一个停止条件。转换到这个问题中就是：我们应该在什么时候将计算完毕的全排列输出出来呢？答案是处理到第n+1个盒子时。在前面的“故事背景”中，我们在走到第四个盒子的位置时，发现这个地方没有盒子，就往回走了。这个时候就是要输出的时候。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int step) {
    if(step==n+1) {
        for(int i=1;i<=n;i++) {
            printf("%d",a[i]);
        }
        printf("\n");
        return;    //返回前一步
    }
    for(int i;i<=n;i++) {
        if(book[i]==0) { 
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
}

  整个过程我们模拟完毕了，整理得到完整的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<cstdio>
#include<iostream>
using namespace std;
int a[10],book[10],n;
void dfs(int step) {
    if(step==n+1) {
        for(int i=1;i<=n;i++) {
            printf("%d",a[i]);
        }
        printf("\n");
        return;    //返回前一步
    }
    for(int i;i<=n;i++) {
        if(book[i]==0) { 
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
}
int main() {
    scanf("%d",&n);
    dfs(1);
    return 0;
}

  这个问题虽然简单，但是包含了dfs的基本模型。理解dfs算法的关键在于理解“当下应该如何去做”。至于“下一步应该怎么做”是和当下的操作一样的。我们在处理第step个盒子和step+1个盒子的时候，都采用的是一样的操作。因此，我们可以整理出dfs的基本模型：

1
2
3
4
5
6
7
void dfs(int step) {
    判断边界
    尝试所有的可能 for(int i=1;i<=n;i++) {
        继续下一步 dfs(step+1)
    }
    返回
}

  我们以一道题目为例，第七届蓝桥杯的第七题，剪邮票：

如【图1.jpg】, 有12张连在一起的12生肖的邮票。
现在你要从中剪下5张来，要求必须是连着的。
（仅仅连接一个角不算相连）
比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。
请你计算，一共有多少种不同的剪取方法。
请填写表示方案数目的整数。
注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。


图1


图2


图3

  我们先看一下一位同学错误的解法吧：http://blog.csdn.net/star92014/article/details/50942239

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<stdio.h>
int a[5]={0,};

int check(){
    int flag[5]={0,};
    flag[0]=1;
    int check[5]={0,};
    int i,j;

rep:    
    for(i=0;i<5;i++){
        if(flag[i]&&check[i]==0){
            check[i]=1;
            for(j=0;j<5;j++){
                if(j==i)continue;
                if(a[j]==a[i]+1||a[j]==a[i]-1
                ||a[j]==a[i]-4||a[j]==a[i]+4){
                    flag[j]=1;
                }
            }   
        }
    }

    for(i=0;i<5;i++){
        if(flag[i]&&check[i]==0)goto rep;
    }
    int count=0;
    for(i=0;i<5;i++){
        if(flag[i])count++;
    }
    if(count==5)return 1;
    else return 0;
}
int main(){
    int count=0;
    for(a[0]=1;a[0]<13;a[0]++){
        for(a[1]=a[0]+1;a[1]<13;a[1]++){
    //  if(a[1]==a[0])continue;
        for(a[2]=a[1]+1;a[2]<13;a[2]++){
    //  if(a[2]==a[0]||a[2]==a[1])continue;
        for(a[3]=a[2]+1;a[3]<13;a[3]++){
    //  if(a[3]==a[0]||a[3]==a[1]||a[3]==a[2])continue;
        for(a[4]=a[3]+1;a[4]<13;a[4]++){
        //if(a[4]==a[0]||a[4]==a[1]||a[4]==a[2]||a[4]==a[3])continue;
        if(check()){
            printf("%d %d %d %d %d\n",a[0],a[1],a[2],a[3],a[4]);
        count++;
        }
    }
    }
    }
    }
    }

    printf("%d",count);
    return 0;
}

  代码质量不说，这位同学得到的答案是202，是错误的。那么问题出在了哪里呢？是序列的重复问题。比如12345和12354。为了避免这种情况，我们除了增加判断条件之外，还可以从数据上入手，将序列改为{1,2,3,4,6,7,8,9,11,12,13,14};这样，在判断换行之后的左右侧元素时，就会有失效的元素，避免了重复。下面是代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <cstring>
using namespace std;
int dir[4] = {1,-1,5,-5};
int temp1[12] = {1,2,3,4,6,7,8,9,11,12,13,14};
int temp2[5];
int vis[5];
int ans = 0;
void dfs(int u){
    for(int i=0 ;i<4 ;i++){
        int t = temp2[u]+dir[i];
        if(t>=1&&t<=14){
            for(int j=0 ;j<5 ;j++)
                if(t==temp2[j]&&!vis[j]){
                    vis[j]=1;
                    dfs(j);
                }
        }
    }
}
int main(){
    for(int a=0 ;a<12 ;a++){
        for(int b=a+1 ;b<12 ;b++){
            for(int c=b+1 ;c<12 ;c++){
                for(int d=c+1 ;d<12 ;d++){
                    for(int e=d+1 ;e<12 ;e++){
                        temp2[0]=temp1[a];
                        temp2[1]=temp1[b];
                        temp2[2]=temp1[c];
                        temp2[3]=temp1[d];
                        temp2[4]=temp1[e];
                        //初始化访问标记数组
                        memset(vis,0,sizeof(vis));
                        vis[0]=1;
                        dfs(0);
                        //连通性判断
                        int flag = 1;
                        for(int i=0 ;i<5 ;i++){
                            if(vis[i]==0){
                                flag = 0;
                            }
                        }
                        if(flag)ans++;
                    }
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

  DFS专项练习：http://www.z16388.top/2017/03/30/dfs/