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

全排列

  什么是全排列?就是一组数据所有可能的排列顺序。如果使用暴力枚举的方法,需要对每一个位置都进行一次循环,如果有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/