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

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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