网站建设的标准,高档网站建,wordpress 长腿蜘蛛,优化营商环境条例目录
前言
1#xff0c;普通DFS实现1~n的元素全排列
2#xff0c;计数器DFS实现重复元素全排列
总结 前言 我们之前看到的全排列问题的解法都是通过交换法达到的#xff0c;去重的效果也是通过判断当前元素前是否有相同元素来实现#xff0c;今天我们带来一个全新的思路…目录
前言
1普通DFS实现1~n的元素全排列
2计数器DFS实现重复元素全排列
总结 前言 我们之前看到的全排列问题的解法都是通过交换法达到的去重的效果也是通过判断当前元素前是否有相同元素来实现今天我们带来一个全新的思路使我们直接进行深度优先搜索一个计数器就可以实现不用交换。 1普通DFS实现1~n的元素全排列 我们先一步一步来先从1~n不重复的开始 假如说我们现在的n是3则有以下排列组合 1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
仔细观察思考一下我们列举这些排列组合的时候是不是我们先固定了一个数字为基准之后把剩下的数字进行全排列呢那再继续往下说我们在把剩下的数字全排列的时候是不是也会跟前面一样以一个数字为基准呢我们推理一下
第一次
固定 1 1 在2 3里面选固定21 2 在3里面选固定31 2 3 排列出来了
以此类推我们发现这样刚好适合使用递归和回溯算法来实现我们在排列出来之后跳出递归之后进行回溯位数作为我们的参数理解一下代码
#include iostreamusing namespace std;int num[11], mark[11], n;void dfs(int p) {if (p n 1) {for (int i 1; i n; i) {cout num[i] ;}cout endl;return;}for (int i 1; i n; i) {if (mark[i] 0) {num[p] i;mark[i] 1;dfs(p 1);mark[i] 0;}}
}int main() {cin n;dfs(1);return 0;
}
这里我们使用一个mark数组来记录这个数字有没有在上一层递归中已经被选择过。
但是当我们输入的是自定义数组且有重复元素的时候这个方法就失效了。
2计数器DFS实现重复元素全排列
我们设想如果说我们给出一个有重复元素的数组 1 2 2 1它的重复排列是因为什么答案是如果以数值为判断标准他们两个其实并没有区别如果是交换法那么以下标为判断标准第一个2跟第二个2下标虽不同但是如果与第一个交换答案还是一样的。所以我们找另一种规律那就是数量。我们发现这个数组中每种数字的数量是不一样的这样的话我们每次判断这个数字用没用完就可以了
void dfs(int p) {if (p a.size()) { // 位数到了for (int t : a) {cout t ;}cout endl;return;}for (int t : num) {if (cot[t] 0) { // 判断是否要用这个数纯靠计数器a[p] t;cot[t]--;dfs(p 1);cot[t]; // 回溯}}}
dfs函数就是这样当我们使用了一个数字之后计数器就减去1回溯时加上1但是它是怎么完成去重的呢
这里如果我们直接使用输入时的数据进行递归那结果是会有重复的因为在我们回溯的时候计数器的个数回拨了但是这个时候循环的元素里又会有一个相同的元素例如
1 2 2 dfs时第一次1 通过 计数器-- 进入递归 1
1 不通过 2 通过 计数器-- 进入递归 1 2
1 不同过 2 通过 计数器-- 跳出递归 1 2 2
对的我没写错其实第三个2没用上因为我们其实只需要数字的种类就可以了但是继续就会出现重复
1 2 2 dfs时第一次最外层递归
1 通过 计数器-- 进入递归 1
1 不通过 2 通过 计数器-- 进入递归 1 2
1 不同过 2 通过 计数器-- 跳出递归 1 2 2回溯1次到了1 的时候此时最外层递归还是1里面的一层第一个 1 和 2已经用掉了回溯了一次所以计数器的次数还剩一次此时循环再次到2不过是第三个2但是因为回溯过所以1 2 2再次出现造成重复。接下来跳出递归后再回溯了一次回到了第二层递归第二层递归循环结束回到了最外层计数器归到2最外层开始了2开头.........之后就是一样的剧本我们通过分析递归了解了是遍历数组时的重复元素造成了结果的重复而且其实我们依靠计数器的话也不需要这些重复的数据只要一开始统计一下个数就好。
这样的话我们输入之后把数组过滤一下1221过滤成12只记录种类
// 统计各个数字的个数for (int i 0; i a.size(); i) {cin n;cot[n];}// 每个数字只添加一个for (int i 0; i cot.size(); i) {if (cot[i] 0) {num.push_back(i);}}sort(num.begin(), num.end());
先排个序可以确保结果也是有序的。
之后我们汇总一下看看整体代码
//
// Created by 33058 on 2023-09-18.
//
#include iostream
#include vector
#include algorithmusing namespace std;vectorint num, cot(10), a(3);void dfs(int p) {if (p a.size()) { // 位数到了for (int t : a) {cout t ;}cout endl;return;}for (int t : num) {if (cot[t] 0) { // 判断是否要用这个数纯靠计数器a[p] t;cot[t]--;dfs(p 1);cot[t]; // 回溯}}}int main() {int n;// 统计各个数字的个数for (int i 0; i a.size(); i) {cin n;cot[n];}// 每个数字只添加一个for (int i 0; i cot.size(); i) {if (cot[i] 0) {num.push_back(i);}}sort(num.begin(), num.end());dfs(0);return 0;
}这个是确位数 a 在 1 a 3 数字n在 0 a 10之间的开数组的时候10和3可以进行n位的推广。
要注意递归的出口一定是a.size()而不是num.size()因为num只记录了数字的种类a才是真正的3位数
总结
至此全部的内容就结束了大家可以仔细的理解代码一步一步剖析递归的过程从位数少的开始这样也就好理解了。
