元素全排列问题的新思路（DFS，递归，计数器）

目录

前言

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 <iostream>using 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 <algorithm>using namespace std;vector<int> 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位数！！

总结

至此全部的内容就结束了，大家可以仔细的理解代码，一步一步剖析递归的过程，从位数少的开始，这样也就好理解了。