啊哈算法之【简单】深度搜索

jws6994

题目已经贴上
【我是题目】输入一个数n，输出1~n的全排列，每个数只出现一次，例如输入3表示输出1~3的全排列：123、132、213、231、312、321，要求写个程序，能够满足输入一个数n（1~9）之后打印出这个1~n的全排列可能性。代码如下

[C] 纯文本查看 复制代码

int a[10], book[10], n;//此处特别说明下：C语言的全局变量在没有赋值前默认为0，因此这里的book数组无需全部再次赋初值0
//step代表现在在第几个盒子前面
        void dfs (int step) {
            int i;
            if (step == n+1) {
                //如果站在第n+1个盒子前面，则表示前n个盒子已经放好扑克牌
                //输出一种排列（1~n号盒子中的扑克牌编号）
                for (i = 1; i <= n; i++) {
                    printf("%d", a[i]);
                }
                printf("\n");
                return;//返回之前的一步（最近一次调用dfs函数的地方）
            }
            //此时站在第step个盒子面前，应该放那张牌呢
            //按照1，2，3。。。n的顺序一一尝试
            for (i = 1; i <= n; i++) {
                //判断扑克牌i是否在手上
                if (book[i] == 0) {
                    //开始尝试使用扑克牌
                    a[step] = i;//将i号扑克牌放入第step号盒子中
                    book[i] = 1;//将book[i]等于0表示i号扑克牌在手上

                    //第step个盒子已经放好了扑克牌，接下来需要走到下一个盒子前面
                    dfs(step+1);//这是通过函数的递归调用实现的（最近调用自己）
                    book[i] = 0;//这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一次尝试
                }
            }
            return;
        }

有点懵懂为什么最后递归结束还要 book=0，收回去，求大佬解答

zyx1211

dfs是一条路走到头 走完没找到符合条件的就回退一步 所以要把访问过的节点重新设置为未访问过book=0

jws6994

zyx1211 发表于 2021-5-27 13:53
dfs是一条路走到头 走完没找到符合条件的就回退一步 所以要把访问过的节点重新设置为未访问过book=0

回退一步那不是执行跟上次一样的流程吗？ 就是这一块有点不清楚

侃遍天下无二人

不要光贴代码，写一下题目，这个应该是动态规划问题，写了题目能针对分析

jws6994

侃遍天下无二人 发表于 2021-5-27 14:47
不要光贴代码，写一下题目，这个应该是动态规划问题，写了题目能针对分析

大佬，题已经贴上去了，有空可以看下，谢谢

侃遍天下无二人

我不是特别喜欢这种表达方式，容易把人弄糊涂
首先，务必要明确的一点是，当程序输出全排列时，已经递归到n+1层
例如n=3时，输出第一个全排列的过程中，各层刚刚调用下层函数时的状态如下：
（我觉得a更像一个栈，所以多出的0就不写了）

层级	a	book（各层共享）	for循环的i值（各层独立）
1	{1}	{1,0,0,0,0,0,0,0,0,0}	1
2	{1，2}	{1,1,0,0,0,0,0,0,0,0}	2
3	{1，2， 3}	{1,1,1,0,0,0,0,0,0,0}	3

问题就出在这个book是各层共享的变量，如果不将book中的值清零，当函数退回前一层的时候，状态就会是这样

层级	a	book（各层共享）	for循环的i值（各层独立）
x	{[x-1个数]}	{1,1,1,0,0,0,0,0,0,0}	？

如果是在第1层，？在2～n（此处为3）之间，如果在其他层，？在1～n之间。
这个时候就无法向a中加入任何数了，因为所有的数看上去似乎都已经分配了
而实际上并非如此，当函数回退到上一层的时候，便是为寻找新的全排列做准备，因此其选定的数必须释放，故要将book对应处置为0.
此外，各层的i值是相互独立的，如果上层的i没发生变动，本层的i就只能增大，上层的i发生变动后，本层的i会重新计数，这就类似于数数的过程了，n=3时，相当于按3进制（逢三进一）从000数到222，自然各层i值的组合不会有重复的情况。book的作用在于过滤数字重复的情况

侃遍天下无二人

如果把a看成一个栈Stack，把book看成一个集合Set，代码会显得清晰很多，我等会给你整一个Java版的，C++里也有栈和集合

[Java] 纯文本查看 复制代码

import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class test {
    Stack<Integer> a;
    Set<Integer> book;

    //构造函数
    public test() {
        this.a = new Stack<>();
        this.book = new TreeSet<>();
    }

    private void dfs(int step, int n){
        if(step==n+1){
            System.out.println(a);
            return;
        }
        for(int i=1;i<=n;i++){
            //如果当前数字没被选择过
            if(!book.contains(i)){
                a.push(i);//将当前数字入栈
                book.add(i);//记录当前数字
                dfs(step+1, n);//深入递归
                book.remove(i);//释放选择的数字
                a.pop();//被释放的数字不应该在组合中
            }
        }
    }

    public static void main(String[] args) {
        test t = new test();
        t.dfs(1,3);
    }
}

运行输出：


[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Process finished with exit code 0

h88782481

c++中有全排列函数，可以拿去直接用

[C++] 纯文本查看 复制代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        a[i] = i + 1;
    }
    sort(a, a + n);
    do
    {
        for (int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    } while (next_permutation(a, a + n));
    return 0;
}

jws6994

侃遍天下无二人 发表于 2021-5-27 15:54
如果把a看成一个栈Stack，把book看成一个集合Set，代码会显得清晰很多，我等会给你整一个Java版的，C++里也 ...

谢谢，我拿去看看

jws6994

h88782481 发表于 2021-5-27 16:06
c++中有全排列函数，可以拿去直接用
[mw_shl_code=cpp,true]#include
using namespace std;

其实，我不懂C++，我贴的是从网上找到的demo，想自己理解之后写一个java版本的，主要是明白思路，代码慢慢写