数组合数学

SJT算法：沿哈密顿路径枚举全排列

字数统计: 1.9k字   |   阅读时长: 7分
, , , ,

摘要: 枚举全排列与哈密顿路径

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

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

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

除了回溯法以外，还可以从两个全排列之间的关系出发，形成枚举全排列的算法。例如如果全排列的元素之间可以比较大小，那么排列之间就可以定义字典序，于是两个排列之间就有了大小关系，多个排列也可以进行排序。此时按照字典序走一遍，也可以枚举全排列，参考文章 字典序法枚举排列)。

本文我们看一种新的思路，将 $n!$ 个 $n$ 位全排列抽象为 $n!$ 节点的哈密顿图，走一遍哈密顿路径即可枚举全排列。

全排列抽象为哈密顿图节点

将全排列抽象为图中的节点，那么 $n!$ 个全排列形成一个 $n!$ 节点的图，如果两个排列之间，是其中一个排列交换了相邻元素形成另一个排列的关系，我们认为这两个排列是相邻的，在图中相应的节点连边。可以证明，这样的图是哈密顿图，那么走一遍哈密顿路径自然就枚举了所有的全排列了。

我们首先看一下将全排列抽象为哈密顿图节点的过程。考虑以下问题：

设 $G_{n}$ 是一个图，其节点集合是 $\{1, 2, \cdots, n\}$ 上的所n 位有排列。当且仅当两个排列 $a_{1}, a_{2}, \cdots, a_{n}$ 与 $b_{1}, b_{2}, \cdots, b_{n}$ 互换了两个相邻位置上的元素时，这两个排列对应的节点才有连边。
证明：$G_{n}$ 是哈密顿图。

证明

n = 1 时，图中只有一个节点，自然是哈密顿图。

假设 n = k 成立，也就是 $n \leq k$ 时 $G_{n}$ 是哈密顿图。

下面看 $n = k + 1$ 的情况。推导过程与 SJT 算法一样，也就是说 SJT 算法就是这个问题的构造性证明。下面我们看推导过程。

拆分为两两不相交的子图

考察 1 ~ k 的某个排列 $P_{k}$，下面在 $P_{k}$ 中插入 $k+1$，共有 $k+1$ 个位置，对应地可以形成 $k+1$ 个 1~k+1 的排列，对应 $G_{k+1}$ 中的 $k+1$ 个节点，这 $k+1$ 个节点形成一个子图 $G’$。

$P_{k}$ 共有 $k!$ 种，对每个 $P_{k}$ 我们都走一遍插入 $k+1$ 的过程，总共可以得到 $(k+1)!$ 个 1~k+1 的排列，于是 $G_{k+1}$ 就被分成了两两不相交的 $k!$ 个子图，每个子图 $k+1$ 个节点。

子图内部存在哈密顿路径

对于某个 1~k 的排列 $P_{k}$，首先把 $k+1$ 放最后一个位置，对应的排列为 $P_{k}, k+1$，然后一直交换 $k+1$ 与前一个位置的元素，直至 $k+1$ 交换到第一个位置，最后形成的排列就是 $k+1, P_{k}$。

以 $P_{k} = 1, 2, 3, \cdots, k$，交换过程如下：

1
2
3
4
5
6
7
1, 2, 3, ..., k-1, k, k+1
1, 2, 3, ..., k-1, k+1, k
1, 2, 3, ..., k+1, k-1, k
...
1, 2, k+1, ..., k-2, k-1, k
1, k+1, 2, ..., k-2, k-1, k
k+1, 1, 2, ..., k-2, k-1, k

这就是子图内部的哈密顿路径。

当然也可以反过来，首先把 $k+1$ 放第一个位置，然后一直交换 $k+1$ 与后一个位置的元素，直至 $k+1$ 交换到最后一个位置，最后形成的排列为 $P_{k}, k+1$，这与前面的是同一条哈密顿路径。

构造哈密顿回路

有 $k!$ 个子图，按照前面的构造方法，就对应地有 $k!$ 条哈密顿路径，下面我们把这些哈密顿路径依次相连，形成一条回路，构造方法如下：

其中 $P_{k}[i]$ 表示 $G_{k}$ 中的哈密顿回路中的第 $i$ 个节点对应的排列。

  • 从 $P_{k}[i], k+1$ 到 $k+1, P_{k}[i]$ 的过程就是前面的构造子图 $G’$ 的哈密顿路的过程。
  • 从 $P_{k}[i], k+1$ 到 $P_{k}[i+1], k+1$ 的过程就是归纳假设中 $G_{k}$ 的哈密顿回路。

因此，以上过程就构造了 $G_{k+1}$ 的一条哈密顿路。这条哈密顿路的收尾节点 $P_{k}[1], k+1$ 和 $P_{k}[k!], k+1$ 对应的排列是交换了一个相邻元素的关系，原因在于按照归纳假设 $G_{k}$ 是哈密顿图，因此 $P_{k}[1]$ 与 $P_{k}[k!]$ 是交换了一个相邻元素的关系。

于是刚刚构造的 $G_{k+1}$ 的哈密顿路也是哈密顿回路。因此 $G_{n}$ 是一个哈密顿图。

$\Box$

枚举 n 位全排列的 SJT 算法

问题

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

提示：

1
2
3
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

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

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

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

算法

思路与前面的问题的证明过程一样，下面是具体的算法。

每个元素赋予一个方向，初始状态: $1(\leftarrow), 2(\leftarrow), 3(\leftarrow), …, n(\leftarrow)$

定义可移动数: 一个数指向一个比它小的数，该数是可移动数

1
2
3
4
step1: 找到最大的可移动数 m
step2: 交换 m 和 m 指向的数
step3: 改变所有比 m 大的数的方向
重复 step1~step3，直至找不到可移动数

代码 (模板、C++)

SJT 算法不能处理重复元素。

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
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > result;
        if(nums.empty()) return result;
        int n = nums.size();
        vector<int> ori(n, 0); // 1 右，0 左
        sort(nums.begin(), nums.end());
        int minx = nums[0];
        while(true)
        {
            result.push_back(nums);
            int m = minx - 1;
            int k = -1;
            for(int i = 0; i < n; ++i)
            {
                if((i < n - 1  && ori[i] == 1 && nums[i + 1] < nums[i])
                        || (i > 0 && ori[i] == 0 && nums[i - 1] < nums[i]))
                {
                    if(nums[i] > m)
                    {
                        m = nums[i];
                        k = i;
                    }
                }
            }
            if(k == -1)
                break;
            if(ori[k] == 0)
            {
                swap(nums[k], nums[k - 1]);
                swap(ori[k], ori[k - 1]);
            }
            else
            {
                swap(nums[k], nums[k + 1]);
                swap(ori[k], ori[k + 1]);
            }
            for(int j = 0; j < n; ++j)
            {
                if(nums[j] > m)
                    ori[j] ^= 1;
            }
        }
        return result;
    }
};
Share