字典序法枚举排列

摘要: 按照字典序来枚举全排列

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 回溯法的思想、设计与分析 中，我们系统学习了回溯法。回溯法将解空间看做树形结构，称为状态空间树，在文章 回溯法三种常见的状态空间树：子集树、排列树、满m叉树 中我们串讲了几种重要的状态空间树，排列树就是其中非常重要的一种。

利用回溯法，我们可以枚举全排列，有重复元素的全排列和无重复元素的全排列都可以枚举，参考文章 常见的枚举方式。

除了回溯法以外，还可以从两个全排列之间的关系出发，形成枚举全排列的算法。例如将全排列抽象为图中的节点，那么 $n!$ 个全排列形成一个 $n!$ 节点的图，如果两个排列之间，是其中一个排列交换了相邻元素形成另一个排列的关系，我们认为这两个排列是相邻的，在图中相应的节点连边。可以证明，这样的图是哈密顿图，那么走一遍哈密顿路径自然就枚举了所有的全排列了，参考文章 SJT算法：沿哈密顿路径枚举全排列。

如果全排列的元素之间可以比较大小，那么排列之间就可以定义字典序，于是两个排列之间就有了大小关系，多个排列也可以进行排序。此时按照字典序走一遍，也可以枚举全排列。

本文我们就来看一下字典序法枚举排列的过程。首先解决给定一个排列找字典序下一个排列的问题，31. 下一个排列，然后持续调用这个过程直至字典序最大的排列，即可枚举全排列。

---

$1 字典序法找下一个排列

• 31. 下一个排列

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须 原地 修改，只允许使用额外常数空间。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]

算法：字典序法

以 A = 12345 为例：

1) 从序列 A 的右端开始向左扫描，直至找到第一个比其右边数字小的数字 $A_{i}$，即 $i = \max\{j|a_{j} < a _{j+1}\}$。

2) 从 $A_{i}$ 右边找出所有比 $A_{i}$ 大的数中最小的数字 $A_{k}$，即 $A_{k} = \min\{a_{j}|a_{j} > a_{i},j > i\}$。

3) 交换 $A_{j}$ 与 $A_{k}$。

4) 将 $A_{i}$ 右边的序列翻转，即可得到字典序的下一个排列。

5) 重复上面的步骤，直至得到字典序最大的排列，可以生成所有全排列。

代码 (C++)

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.empty()) return;
        int n = nums.size();
        if(n == 1) return;
        // 找到从 n-1 开始往左，第一个不单调不降的位置 t
        int t = n - 2;
        while(t >= 0 && nums[t] >= nums[t + 1])
            --t;
        if(t < 0)
            reverse(nums.begin(), nums.end());
        else
        {
            int k = n - 1;
            while(k > t && nums[t] >= nums[k])
                --k;
            swap(nums[t], nums[k]);
            reverse(nums.begin() + t + 1, nums.end());
        }
    }
};

---

$2 枚举排列

• 47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

算法：字典序法 (next_permutation)

从字典序最小的排列出发，持续调用前面已经解决的查找字典序下一个排列的函数，直至走到字典序最大的排列即可。

这种做法可以处理重复元素。

代码 (C++)

为了方便，这里直接用 std::next_permutation。

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int> > result;
        if(nums.empty()) 
            return result;
        sort(nums.begin(), nums.end());
        do{
            result.push_back(nums);
        }
        while(next_permutation(nums.begin(), nums.end()));
        return result;
    }
};

---