输出全排列

输出全排列

各位 22 级的同学,独立思考,不要抄袭,抄袭必被抓~

输入一个数 \(n\),输出 \(1\sim n\) 的所有全排列,每个排列占一行,每个字符之间空一格。勤奋的同学一定已经开始打表了是吧

说是能做肯定不是骗大家,那怎么做呢~

其实回溯法本质还是递归,回想我们做过的小兔子(青蛙)跳台阶的那题,只是需要算出总的方案数就可以,但是这个让你来输出具体的排列,这就需要你来保留每一层递归的状态,所以我们用一个全局数组来完成这一工作(暂且命名为stack,大家可以查一查这个单词什么意思)。

\(n=3\) 为例,一开始stack 是空的,我们需要枚举从 \(1\)\(n\) 这几个数字,填充到 stack[0] 里:

\(\Downarrow\)
1

OK 放进去了,然后考虑后面一个数字,还是从 \(1\)\(n=3\) 枚举:

\(\Downarrow\)
1 1

大家觉得这样行吗?

——你这都跟前面重复了肯定不行啊!

不行是吧,那就换一个 \(2\)

\(\Downarrow\)
1 2

OK 舒服了,再看下一个(我已经试过了,放 \(1\) 不行,\(2\) 也不行,那就放 \(3\)):

\(\Downarrow\)
1 2 3

好的,看看下一个……哎呦怎么满了,那就输出一下叭:

此时你的控制台输出:

1
2
1    2    3

好的我们把 \(3\) 拿掉,往回退一层:

\(\Downarrow\)
1 2

这个 \(2\) 不是从 \(1\) 枚举过来的吗,那还没有枚举完,就还要继续枚举下去:

\(\Downarrow\)
1 3

好的进入下一层从 \(1\) 开始枚举:

\(\Downarrow\)
1 3 1

不行,跟前面重复了,换 \(2\) 试试:

\(\Downarrow\)
1 3 2

好像可以,stack 又满了诶,输出一下:

1
2
3
1    2    3
1 3 2

再把最后一个元素试图换一下 \(3\)

\(\Downarrow\)
1 3 3

不行,死心了,往回退:

\(\Downarrow\)
1 3

呃,第二个元素也举到 \(3\) 了,不能继续举了,只能再退一层,把 \(1\) 换成 \(2\) 试试:

\(\Downarrow\)
2

没啥问题,再放下一个,从 \(1\) 开始枚举:

\(\Downarrow\)
2 1

也没有重复的,再下一个:

\(\Downarrow\)
2 1 1

最后一个放 \(1\) 行吗?不行,重复了。

\(\Downarrow\)
2 1 2

最后一个放 \(2\) 也重复了。

\(\Downarrow\)
2 1 3

那就放 \(3\),一看可以,输出一下:

1
2
3
4
1    2    3
1 3 2
2 1 3

接下来就是周而复始的过程,直到全部都枚举完,你的输出应该是这样的:

1
2
3
4
5
6
7
1    2    3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

我们习惯上把上面的递归过程叫做 DFS(Depth-First-Search),中文叫“深度优先搜索”,就是在一层递归里面有一个循环,每个循环还要跑一个递归,关于 DFS 在数据结构的“图 (Graph)” 部分也会有讲。用“伪代码”(新词汇又来了hhh)描述这个递归是这样的:

  • 参数 len 是进入递归之前 stack 的有效长度,所以最开始调用的时候 len 应该是 0;
  • stackn 被定义为全局变量。
1
2
3
4
5
6
7
8
9
10
11
void dfs(int len) {
if (len == n) {
输出 stack;
return;
}
for (int i = 1; i <= n; i++)
if (i 与 stack[0] 到 stack[len - 1] 的元素都不重复) {
stack[len] = i;
dfs(len + 1);
}
}

对于某一层递归,进入之前已经填充了 len 个,所以检查重复的时候只要从 stack[0] 检查到 stack[len - 1]

可以想见在运行的时候这个 stack 应该是不断伸伸缩缩的,但是在退回上一层的时候并没有删除后面的元素(反正留在那也不影响,因为检查重复是到下标 len - 1,后面的不会被访问到)。

main() 函数里只需要这么写:

1
2
3
4
5
6
int main() {
scanf("%d", &n);
dfs(0);
// 没错我的代码可以很潇洒
return 0;
}

然后再把输出 stack翻译一下:

1
2
3
4
5
void print_stack() {
for (int i = 0; i < n; i++)
printf("%d ", stack[i]);
puts("");
}

翻译一下i 与 stack[0] 到 stack[len - 1] 的元素是否重复,顺序查找,找到了返回 1,找不到返回 0:

1
2
3
4
5
6
7
int find_in_stack(int key, int len) {
for(int i = 0; i < len; i++) {
if (key == stack[i])
return 1;
}
return 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>

int n;
int stack[10];

void print_stack();
void dfs(int len);
int find_in_stack(int key, int len);

int main() {
scanf("%d", &n);
dfs(0);
// 没错我的代码可以很潇洒
return 0;
}

void dfs(int len) {
if (len == n) {
print_stack();
return;
}
for (int i = 1; i <= n; i++)
if (!find_in_stack(i, len)) {
stack[len] = i;
dfs(len + 1);
}
}

void print_stack() {
for (int i = 0; i < n; i++)
printf("%d ", stack[i]);
puts("");
}

int find_in_stack(int key, int len) {
for(int i = 0; i < len; i++)
if (key == stack[i])
return 1;
return 0;
}


输出全排列
https://onlyar.site/2022/01/17/C-Full-arrangement/
作者
Only(AR)
发布于
2022年1月17日
许可协议