我的算法书 - 重复元素的全排列

一句话算法

重复元素全排列就是“每种数只开一个桶”，每个位置从非空桶里取一个数。

问题模型

给定 n 个数，数值可能重复，要求按字典序输出所有不同的排列。

例如输入：

3
1 1 2

不同排列只有：

1 1 2
1 2 1
2 1 1

如果把两个 1 当成两个不同元素，普通全排列会生成：

1(1) 1(2) 2
1(2) 1(1) 2

这两行在数值上完全相同，所以必须去重。

核心直觉

普通全排列的问题在于：它把“第一个 1”和“第二个 1”当成不同物品。

去重的关键是不要再区分这些相同元素。我们把所有相同的数放入同一个桶：

value[i]：第 i 个桶代表的数值；
cnt[i]：这个桶里还剩多少个数。

DFS 填第 pos 个位置时，只枚举“桶”，不枚举“具体是哪一个相同元素”。这样同一个数值排列只会走出一条搜索路径。

“为什么先排序”

先排序再压缩桶，可以让 value 本身有序。DFS 按桶顺序枚举时，输出自然就是字典序。

算法步骤

读入数组并排序。
把相同数字压缩到同一个桶，得到 value[] 和 cnt[]。
定义 dfs(pos)：
- 如果 pos == n，输出当前排列。
- 否则从小到大枚举每个桶 i。
- 若 cnt[i] > 0，把 value[i] 放到 path[pos]，cnt[i]--。
- 递归 dfs(pos + 1)。
- 回溯时恢复 cnt[i]++。

如果题目要求先输出方案数，可以用组合数计算：

\frac{n!}{c_1!c_2!\cdots c_m!}

其中 c_i 是第 i 种数字出现次数。

也可以理解为：先给第一种数选择 c_1 个位置，再给第二种数选择 c_2 个位置，依次进行。

算法证明

关键不变量： 进入 dfs(pos) 时，path[0..pos-1] 是一个合法的不重复排列前缀，且每个桶的 cnt 正好表示还未使用的数量。

初始时前缀为空，所有元素都还在桶中，不变量成立。
每次只从 cnt[i] > 0 的桶取一个数，所以不会使用超过原数量的元素。
递归返回后把这个数放回桶，其他分支看到的状态仍然正确。
到 pos == n 时，所有位置都填满，且每种数使用次数恰好等于输入中的出现次数，所以得到一个合法排列。

再证明“不重不漏”：

不重复： 相同数在同一个桶里。某个排列的第 pos 位若是 x，DFS 只能选择代表 x 的那一个桶，不存在“选择第一个 x”或“选择第二个 x”的差别。
不遗漏： 任意一个合法排列，从左到右看它的每一位。第 pos 位是 x 时，对应桶中一定还有一个 x 可取，所以 DFS 能沿着这条选择路径生成它。

因此算法生成的每个排列不同，且所有不同排列都会被生成。

复杂度分析

设不同排列数量为：

P = \frac{n!}{c_1!c_2!\cdots c_m!}

时间复杂度： $O(nP)$ ，因为输出每个排列需要 $O(n)$ 。
空间复杂度： $O(n + m)$ ，其中 m 是不同数字个数，用于桶、当前路径和递归栈。

代码实现

cpp

        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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

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

// 统计多重集合的不同排列数量。
// n 较小时可以直接使用组合数表，逻辑最直观。
template <class T>
long long count_distinct_permutations(vector<T> a) {
    sort(a.begin(), a.end());

    vector<int> freq;
    for (int i = 0; i < (int)a.size(); ) {
        int j = i;
        while (j < (int)a.size() && a[j] == a[i]) ++j;
        freq.push_back(j - i);
        i = j;
    }

    int n = (int)a.size();
    vector<vector<long long>> C(n + 1, vector<long long>(n + 1, 0));
    for (int i = 0; i <= n; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }

    long long ans = 1;
    int remaining = n;
    for (int c : freq) {
        ans *= C[remaining][c];
        remaining -= c;
    }
    return ans;
}

// 枚举多重集合的所有不同排列。
// 先排序后压缩成 value + cnt，再用 DFS 按桶取数。
template <class T, class Emit>
void enumerate_multiset_permutations(vector<T> a, const Emit& emit) {
    sort(a.begin(), a.end());

    vector<T> value;
    vector<int> cnt;
    for (const auto& x : a) {
        if (value.empty() || value.back() != x) {
            value.push_back(x);
            cnt.push_back(1);
        } else {
            ++cnt.back();
        }
    }

    vector<T> path(a.size());

    auto dfs = [&](auto&& self, int pos) -> void {
        if (pos == (int)a.size()) {
            emit(path);
            return;
        }

        for (int i = 0; i < (int)value.size(); ++i) {
            if (cnt[i] == 0) continue;
            --cnt[i];
            path[pos] = value[i];
            self(self, pos + 1);
            ++cnt[i];
        }
    };

    if (a.empty()) {
        emit(path);
        return;
    }

    dfs(dfs, 0);
}

测试用例

输入：

3
1 1 2

输出：

应用分类详解

重复元素全排列的本质是：枚举顺序，但相同元素不可区分。

一、含重复物品的排列输出

典型模式： 给定若干数字或字符，元素可能重复，要求输出所有不同排列。

识别信号： 题面出现“可能重复”“不同排列”“按字典序输出”。

核心建模： 把相同值压成桶，DFS 每层选择一个非空桶。

应用场景	经典题目	核心思路
重复数字排列	本页题目	`value + cnt` 压缩后回溯
重复字符排列	leetcodecn-47	与数字完全相同，只是值类型换成字符或整数

二、组合计数和枚举结合

典型模式： 不仅要输出方案，还要先输出方案数量。

识别信号： 要求“第一行输出方案数”，后面再输出具体方案。

核心建模： 用 $\frac{n!}{c_1!c_2!\cdots c_m!}$ 计算总数，用同一个桶状态 DFS 输出方案。

应用场景	经典题目	核心思路
多重集合排列计数	竞赛基础题	先组合计数，再 DFS 输出
字典序方案生成	排列输出题	排序后按桶顺序枚举

经典例题

leetcodecn-47 全排列 II：重复元素全排列的标准题。
luogu-P1706 全排列问题：先掌握互异元素排列，再对比本页去重方法。
重复字符排列：把字符排序并压缩计数，写法与本模板一致。

参考

本书相关章节：全排列