分享程序员开发的那些事...
更新时间：2022-10-02 23:01:08
输入一个数n，输出1~n的全排列
假设有编号为1,2,3的3张扑克牌和编号为1,2,3的3个盒子。需要将这3张扑克牌分别放到3个盒子里面，并且每个盒子有且只能放一张扑克牌。问一共有多少种放法？
首先，我们按照正常的顺序来进行放置，顺序为——“1-2-3”
然后我们走到了第四个盒子前，这时候已经没有扑克牌可以放置了，现在我们要重新回到3号盒子前，需要取回之前放在3号盒子里的扑克牌，再去尝试看看能不能放别的扑克牌，从而产生一个新的排列。于是我们取回3号扑克牌。
但这时候我们发现手中仍然只有3号扑克牌，没有别的选择，我们不得不回到2号盒子前收回2号扑克。现在我们手里有2张扑克牌，分别是2,3.按照之前约定的顺序（每次到一个盒子前，先放1号，再放2号，最后放3号）我们需要往2号盒子里面放3号扑克牌（上一次放的是2号扑克牌）。放好后来到三号盒子前，将手中仅剩的2号扑克牌放入3号盒子中，又来到了4号盒子面前（不存在），这时候产生了新的排列——“1.3.2”
按照这样的步骤去模拟，我们便会产生所有的排列
for(i = 1;i <= n;i++) { if(book[i] == 0) { a[step] = i; //book[i] 等于0表示第i号扑克还在手上 book[i] = 1; //表明book[i]已经不在手上 } }
使用book数组来标记哪些数组已经使用了
将这串代码封装成一个函数，用同样的方式去处理step+1个盒子
void dfs(int step) //step表示现在站在第几个盒子前面 { //处理第step个小盒子 for (i = 1; i <= n; i++) { if (book[i] == 0) //book[i] 等于0表示第i号扑克还在手上 { a[step] = i; //将第i号扑克放入第step个盒子中 book[i] = 1; //表明book[i]已经不在手上 } } return; }
处理第step+1个小盒子的方法就是dfs（step+1）
void dfs(int step) //step表示现在站在第几个盒子前面 { //处理第step个小盒子 for (i = 1; i <= n; i++) { if (book[i] == 0) //book[i] 等于0表示第i号扑克还在手上 { a[step] = i; //将第i号扑克放入第step个盒子中 book[i] = 1; //表明book[i]已经不在手上 dfs(step + 1); //这里用函数递归的调用来实现（自己调用自己） book[i] = 0; //这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一步尝试 //如果不把刚才放入小盒子的扑克牌收回，那将无法再进行下一步的摆放 //当step = n + 1时，表明前n个盒子都已经放好扑克了 } } return; }
上面代码中的 book[i] = 0 这条语句非常重要，这句话的作用是将小盒子中的扑克牌收回，因为在一次摆放尝试结束返回的时候，如果不把刚才放入小盒子中的扑克牌收回，那将无法进行下一次摆放。
当我们处理到第n+1个盒子的时候，证明我们前n个已经排序完毕，将他们打印出来即可。
打印完毕一定要return，否则会无休止地运行下去。
//深度优先搜索 int a[10], book[10], n; //C语言的全局变量在没有赋值以前默认为0 //因此这里的book数组无需再全部赋值初始值0 //将放牌封装成一个函数 void dfs(int step) //step表示现在站在第几个盒子前面 { int i; if (step == n + 1) //如果站在第n+1个盒子前，表明前n个盒子都已经完成了放置 { //输出一种排列 for (i = 1; i <= n; i++) printf("%d", a[i]); printf("\n"); return; //返回之前最近的一步（最近一次调用dfs的地方） //打印完要立即return，否则会无限循环下去 } //处理第step个小盒子 for (i = 1; i <= n; i++) { if (book[i] == 0) //book[i] 等于0表示第i号扑克还在手上 { a[step] = i; //将第i号扑克放入第step个盒子中 book[i] = 1; //表明book[i]已经不在手上 dfs(step + 1); //这里用函数递归的调用来实现（自己调用自己） book[i] = 0; //这是非常重要的一步，一定要将刚才尝试的扑克牌收回，才能进行下一步尝试 //如果不把刚才放入小盒子的扑克牌收回，那将无法再进行下一步的摆放 //当step = n + 1时，表明前n个盒子都已经放好扑克了 } } return; } int main() { scanf("%d", &n); //输入时要注意为1-9之间的整数 dfs(1); //首先站在1号小盒面前 return 0; }
深度优先搜索（Depth First Search,DFS）
理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步该如何做”，则与“当下该如何做”是一样的。
void dfs(int step) { 判断边界 尝试每一种可能 for(i = 1;i <= n;i++) { 继续下一步的尝试 dfs（step+1） } 返回 }
每一种尝试就是一种“扩展”。每次站在一个盒子前面的时候，都有n种扩展方法，但不是每一种方法都能够成功扩展。
这就是今天的全部内容啦，如果觉得有帮助，请