洛谷P1706 全排列题解

P1706 全排列问题

题目描述

按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

一个整数 $n$ 。

输出格式

由 $\sim n$ 组成的所有不重复的数字序列，每行一个序列。

每个数字保留 $5$ 个场宽。

输入输出样例 #1

输入 #1

输出 #1

	1    2    31    3    22    1    32    3    13    1    23    2    1

说明/提示

$\leq n \leq 9$ 。

这个问题呢，是很明显的DFS（深度优先搜索）的问题，如果你们不了解DFS，可以自己去上网查。我简单的说一下概念：

DFS是一种用于遍历或搜索树或图的算法，其核心思想是"尽可能深"地搜索图的分支。当节点v的所在边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。

可能有些人懵了，所以，说白了就是： $\color{red}不撞南墙不回头$

再简单点：

为了求得问题的解，先选择某一种可能情况向前探索；
在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；
如此反复进行，直至得到解或证明无解。

DFS的操作步骤

1.假设一个数组a[5][5]，零代表墙，一代表路，初始点是a[1][1]，要到达a[n][n]。

假如数组为：

dfs方式如下：

大家应该也比较了解DFS了吧，那我们便开始讲题；

做题目的第一步：搞好DFS前要条件

#include<bits/stdc++.h>
using namespace std;
int n, a[15], book[15];
/*我们将题目的输入变量 n 定义出来；
a 数组是排列的结果，book 数组是标记某个数字有没有用 */
int main(){cin >> n;return 0;
}

做题目的第二步：做好DFS边界处理

#include<bits/stdc++.h>
using namespace std;
int n, a[15], book[15];
/*我们将题目的输入变量 n 定义出来；
a 数组是排列的结果，book 数组是标记某个数字有没有用 */
void dfs(int x){if(x > n){//代表已经可以了，所有的数字都排好了for(int i = 1; i <= n; i ++){cout << setw(5) << a[i];//题目要求5个场宽}cout << endl;return ;//回溯（返回）}}
int main(){cin >> n;return 0;
}

做题目的第三步：写好DFS数组排列

#include<bits/stdc++.h>
using namespace std;
int n, a[15], book[15];
/*我们将题目的输入变量 n 定义出来；
a 数组是排列的结果，book 数组是标记某个数字有没有用 */
void dfs(int x){if(x > n){//代表已经可以了，所有的数字都排好了for(int i = 1; i <= n; i ++){cout << setw(5) << a[i];//题目要求5个场宽}cout << endl;return ;//回溯（返回）}for(int i = 1; i <= n; i ++){if(book[i] == 0){//如果这个数没有用过a[x] = i;//标记（x 作为第几位）book [i] = 1; // 这个数用过了dfs(x + 1); //进行下一位的排列book [i] = 0; //回溯时因为新的一轮开始，所以没有用过，重新标记}}
}
int main(){cin >> n;dfs(1);//进行DFSreturn 0;
}

这时候，代码就写完了，没听懂的同学可以看一下模拟过程，听懂的同学可以一键三联吗：

全排列问题的模拟过程

初始状态

n = 3
数组 a = [0, 0, 0, ...] (初始全为0)
标记数组 book = [0, 0, 0, ...] (初始全为0，表示所有数字未被使用)

调用 dfs(1)

dfs(1) - 第一层递归 (x=1)

循环 i 从 1 到 3:

i=1:
- book[1]==0，可以使用
- 设置 a[1]=1
- 标记 book[1]=1
- 调用 dfs(2)
dfs(2) - 第二层递归 (x=2)

循环 i 从 1 到 3:
1. i=1:
  - book[1]==1，跳过
2. i=2:
  - book[2]==0，可以使用
  - 设置 a[2]=2
  - 标记 book[2]=1
  - 调用 dfs(3)
  dfs(3) - 第三层递归 (x=3)
  
  循环 i 从 1 到 3:
  1. i=1:
    - book[1]==1，跳过
  2. i=2:
    - book[2]==1，跳过
  3. i=3:
    - book[3]==0，可以使用
    - 设置 a[3]=3
    - 标记 book[3]=1
    - 调用 dfs(4)
    dfs(4) - 第四层递归 (x=4)
    
    x>n，输出排列: 1 2 3 (每个数字占5个宽度)
    - 返回
  - 回溯: book[3]=0
  - 循环结束
- 回溯: book[2]=0
1. i=3:
  - book[3]==0，可以使用
  - 设置 a[2]=3
  - 标记 book[3]=1
  - 调用 dfs(3)
  dfs(3) - 第三层递归 (x=3)
  
  循环 i 从 1 到 3:
  1. i=1:
    - book[1]==1，跳过
  2. i=2:
    - book[2]==0，可以使用
    - 设置 a[3]=2
    - 标记 book[2]=1
    - 调用 dfs(4)
    dfs(4) - 第四层递归 (x=4)
    
    x>n，输出排列: 1 3 2
    - 返回
  - 回溯: book[2]=0
  1. i=3:
    - book[3]==1，跳过
- 回溯: book[3]=0
- 循环结束

回溯: book[1]=0

i=2:
- book[2]==0，可以使用
- 设置 a[1]=2
- 标记 book[2]=1
- 调用 dfs(2)
dfs(2) - 第二层递归 (x=2)

循环 i 从 1 到 3:
1. i=1:
  - book[1]==0，可以使用
  - 设置 a[2]=1
  - 标记 book[1]=1
  - 调用 dfs(3)
  dfs(3) - 第三层递归 (x=3)
  
  循环 i 从 1 到 3:
  1. i=1:
    - book[1]==1，跳过
  2. i=2:
    - book[2]==1，跳过
  3. i=3:
    - book[3]==0，可以使用
    - 设置 a[3]=3
    - 标记 book[3]=1
    - 调用 dfs(4)
    dfs(4) - 第四层递归 (x=4)
    
    输出排列: 2 1 3
    - 返回
  - 回溯: book[3]=0
- 回溯: book[1]=0
1. i=2:
  - book[2]==1，跳过
2. i=3:
  - book[3]==0，可以使用
  - 设置 a[2]=3
  - 标记 book[3]=1
  - 调用 dfs(3)
  dfs(3) - 第三层递归 (x=3)
  
  循环 i 从 1 到 3:
  1. i=1:
    - book[1]==0，可以使用
    - 设置 a[3]=1
    - 标记 book[1]=1
    - 调用 dfs(4)
    dfs(4) - 第四层递归 (x=4)
    
    输出排列: 2 3 1
    - 返回
  - 回溯: book[1]=0
  1. i=2:
    - book[2]==1，跳过
  2. i=3:
    - book[3]==1，跳过
- 回溯: book[3]=0
- 循环结束

回溯: book[2]=0

i=3:
- book[3]==0，可以使用
- 设置 a[1]=3
- 标记 book[3]=1
- 调用 dfs(2)
dfs(2) - 第二层递归 (x=2)

循环 i 从 1 到 3:
1. i=1:
  - book[1]==0，可以使用
  - 设置 a[2]=1
  - 标记 book[1]=1
  - 调用 dfs(3)
  dfs(3) - 第三层递归 (x=3)
  
  循环 i 从 1 到 3:
  1. i=1:
    - book[1]==1，跳过
  2. i=2:
    - book[2]==0，可以使用
    - 设置 a[3]=2
    - 标记 book[2]=1
    - 调用 dfs(4)
    dfs(4) - 第四层递归 (x=4)
    
    输出排列: 3 1 2
    - 返回
  - 回溯: book[2]=0
- 回溯: book[1]=0
1. i=2:
  - book[2]==0，可以使用
  - 设置 a[2]=2
  - 标记 book[2]=1
  - 调用 dfs(3)
  dfs(3) - 第三层递归 (x=3)
  
  循环 i 从 1 到 3:
  1. i=1:
    - book[1]==0，可以使用
    - 设置 a[3]=1
    - 标记 book[1]=1
    - 调用 dfs(4)
    dfs(4) - 第四层递归 (x=4)
    
    输出排列: 3 2 1
    - 返回
  - 回溯: book[1]=0
  1. i=2:
    - book[2]==1，跳过
  2. i=3:
    - book[3]==1，跳过
- 回溯: book[2]=0
1. i=3:
  - book[3]==1，跳过
- 循环结束