下一个排列

问题描述

这道题是 LeetCode 31题。

“下一个排列”的定义是：给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

我们可以将该问题形式化地描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数。如 123 下一个更大的数为 132。如果没有更大的整数，则输出最小的整数。

以 1,2,3,4,5,6 为例，其排列依次为：

123456
123465
123546
...
654321

可以看到有这样的关系：123456 < 123465 < 123546 < ... < 54321。

算法推导

如何得到这样的排列顺序？这是本文的重点。我们可以这样来分析：

  1. 我们希望下一个数比当前数大，这样才满足“下一个排列”的定义。因此只需要将后面的「大数」与前面的「小数」交换，就能得到一个更大的数。比如 123456，将 5 和 6 交换就能得到一个更大的数 123465。
  2. 我们还希望下一个数增加的幅度尽可能的小，这样才满足“下一个排列与当前排列紧邻“的要求。为了满足这个要求，我们需要：
    1. 在尽可能靠右的低位进行交换，需要从后向前查找
    2. 将一个尽可能小的「大数」与前面的「小数」交换。比如 123465，下一个排列应该把 5 和 4 交换而不是把 6 和 4 交换
    3. 将「大数」换到前面后，需要将「大数」后面的所有数重置为升序，升序排列就是最小的排列。以 123465 为例：首先按照上一步，交换 5 和 4，得到 123564；然后需要将 5 之后的数重置为升序，得到 123546。显然 123546 比 123564 更小，123546 就是 123465 的下一个排列

以上就是求“下一个排列”的分析过程。

算法过程

标准的“下一个排列”算法可以描述为：

  1. 从后向前查找第一个相邻升序的元素对 (i,j)，满足 A[i] < A[j]。此时 [j,end) 必然是降序
  2. 在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」
  3. 将 A[i] 与 A[k] 交换
  4. 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
  5. 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4

该方法支持数据重复，且在 C++ STL 中被采用。

代码

func nextPermutation(nums []int) {
	if len(nums) <= 1 {
		return
	}

	i, j, k := len(nums)-2, len(nums)-1, len(nums)-1

	// find: A[i]<A[j]
	for i >= 0 && nums[i] >= nums[j] {
		i--
		j--
	}

	if i >= 0 { // 不是最后一个排列
		// find: A[i]<A[k]
		for nums[i] >= nums[k] {
			k--
		}
		// swap A[i], A[k]
		nums[i], nums[k] = nums[k], nums[i]
	}

	// reverse A[j:end]
	for i, j := j, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
}

可视化

以求 12385764 的下一个排列为例：
-w347

首先从后向前查找第一个相邻升序的元素对 (i,j)。这里 i=4，j=5，对应的值为 5，7：
-w382

然后在 [j,end) 从后向前查找第一个大于 A[i] 的值 A[k]。这里 A[i] 是 5，故 A[k] 是 6：
-w391

将 A[i] 与 A[k] 交换。这里交换 5、6：
-w340

这时 [j,end) 必然是降序，逆置 [j,end)，使其升序。这里逆置 [7,5,4]：
-w339

因此，12385764 的下一个排列就是 12386457。

最后再可视化地对比一下这两个相邻的排列（橙色是蓝色的下一个排列）：
-w342

全排列

问题描述

这道题是 LeetCode 46题。

给定一个没有重复数字的序列，返回其所有可能的全排列。比如序列 [1,2,3]，其全排列为：

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解法一：下一个排列

可以不断求下一个排列，直到找到 $n!$ 个排列（前提是没有重复元素）。如果序列中包含重复元素，那么判断条件需要改为“直到下一个排列和第一个排列相同”。

时间复杂度：$O(n×n!)$。需要求 $n!$ 次下一个排列，每求一个需要 $O(n)$。
空间复杂度：$O(n×n!)$。需要保存 $n!$ 个解，每个解所需的空间为 $n$。如果不算保存结果所需的空间，那么空间复杂度为 $O(1)$。

这种方法得到的全排列是字典序升序的。

代码：

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
	res := [][]int{}
	cnt := 1
	for i := 1; i <= len(nums); i++ {
		cnt *= i
	}
	for i := 0; i < cnt; i++ {
		res = append(res, copyNums(nums))
		nextPermutation(nums)
	}
	return res
}

func nextPermutation(nums []int) {
	if len(nums) <= 1 {
		return
	}

	i, j, k := len(nums)-2, len(nums)-1, len(nums)-1

	// find: A[i]<A[j]
	for i >= 0 && nums[i] >= nums[j] {
		i--
		j--
	}

	if i >= 0 {
		// find: A[i]<A[k]
		for nums[i] >= nums[k] {
			k--
		}
		nums[i], nums[k] = nums[k], nums[i]
	}

	// reverse A[j:end]
	for i, j := j, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
}

func copyNums(nums []int) []int {
	tmp := make([]int, len(nums))
	copy(tmp, nums)
	return tmp
}

解法二：回溯遍历法

如果序列元素个数已知，可以手写 n 层循环，求所有元素的全排列。以 3 个元素为例，只需要手写 3 层循环：

length := 3
for i := 0; i < length; i++ {
    for j := 0; j < length; j++ {
        for k := 0; k < length; k++ {
            if i, j, k 都不相同 {
                addToResults([]int{a[i], a[j], a[k]})
            }
        }
    }
}

如果序列元素个数 $n$ 未知，可以利用递归实现回溯过程。递归时，每次选择一个元素加入到当前排列中，然后进入下一层，选择下一个元素。如果已经选择了 $n$ 个元素，那么就得到了一个新的排列。

需要一个数组来标记每个元素是否被使用。在每一层中，需要遍历序列中的每一个元素。如果该元素未被使用，则选择该元素，然后进入下一层；返回当前层时，取消选择该元素（回溯），继续选择下一个可用元素。

时间复杂度：$O(n^n)$，实际是 $T(n+n^2+…+n^n)$。
空间复杂度：$O(n×n!)$。需要保存 $n!$ 个解，每个解所需的空间为 $n$。如果不算保存结果所需的空间，那么空间复杂度为 $O(n)$，即递归的深度。

这种方法得到的全排列是字典序升序的。

代码：

var res [][]int
var flag []bool

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
	res = [][]int{}
	flag = make([]bool, len(nums))
	dfs(nums, []int{})
	return res
}

func dfs(nums, cur []int) {
	if len(cur) == len(nums) {
		res = append(res, copyNums(cur))
		return
	}
	for i := 0; i < len(nums); i++ {
		if flag[i] == false {
			flag[i] = true
			dfs(nums, append(cur, nums[i]))
			flag[i] = false // 回溯
		}
	}
}

解法三：回溯交换法

这种方法的思路最为简单：一个长为 $n$ 的字符串 s，它的所有排列，相当于每个 s[i] 作为第一个元素，然后剩下的 n-1 个字符的所有排列。

时间复杂度：$O(\sum_{k = 1}^{n}{A_n^k})$。
空间复杂度：$O(n×n!)$。需要保存 $n!$ 个解，每个解所需的空间为 $n$。如果不算保存结果所需的空间，那么空间复杂度为 $O(n)$，即递归的深度。

时间复杂度推导

第一层循环 $n$ 次，第二层循环 $n-1$ 次，…，第 n 层循环 1 次。如果将递归过程想象成一棵树，那么第一层递归有 $n$ 个节点，第二层递归有 $n×(n-1)$ 个节点，…，最后一层递归有 $n!$ 个节点。循环的总次数就是树的节点总数： $T(n + n×(n-1) + n×(n-1)×(n-2) + … + n!) = O(\sum_{k = 1}^{n}{A_n^k})$

注意：这种方法得到的全排列不是字典序升序的。

代码要注意：从第一个元素开始交换而不是从第二个元素开始，保证当前序列的每个元素都可以作为开头元素。

实现上有两种方式。一种是每当递归到最后一层时，新增一个结果，这需要使用全局变量保存所有结果。

var res [][]int

func permute(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
	res = [][]int{}
	dfs(nums, 0)
	return res
}

func dfs(nums []int, start int) {
	if start == len(nums)-1 { // 到最后一层再保存结果
		res = append(res, copyNums(nums))
		return
	}
	for i := start; i < len(nums); i++ { // i 从 start 开始
		nums[start], nums[i] = nums[i], nums[start] // 交换
		dfs(nums, start+1)
		nums[start], nums[i] = nums[i], nums[start] // 换回原来的位置，回溯
	}
}

另一种是分治法的思路。对于 n 个字符的全排列，先选出某个字符 s[i]，然后求解子问题 剩下的 n-1 个字符的全排列。然后在子问题每个解的开头加上选出的字符 s[i]，就是当前问题的解了。

func permute(nums []int) [][]int {
	if len(nums) <= 1 {
		return [][]int{nums}
	}
	res := [][]int{}
	for i := 0; i < len(nums); i++ {
		nums[0], nums[i] = nums[i], nums[0] // 将 i 换到第一个位置
		subres := permute(nums[1:])         // 求剩余 n-1 个元素的全排列
		for _, v := range subres {          // n-1 个元素的排列，前面加上 s[0]，得到 n 个元素的排列
			res = append(res, append([]int{nums[0]}, v...))
		}
		nums[0], nums[i] = nums[i], nums[0] // 恢复之前的次序
	}
	return res
}

三种解法对比

解法一、二均能得到按字典序升序的全排列，解法三则不能。

从 LeetCode 实际执行结果来看，三种解法的时间、空间复杂度均不相上下。

全排列（包含重复元素）

如何去重？

这道题是 LeetCode 47题。

如果序列中包含重复元素，上述三种解法该如何修改？

对于解法一，按照下一个排列的规则，当到达最后一个排列后，再下一个排列就是第一个排列。因此只需要不断取下一个排列，直到与第一个排列相等时终止。比较两个排列是否相等需要 $O(n)$，因此时间复杂度变为 $O(n^2 ×n!)$。代码略。

对于解法二和解法三，需要在每层递归中不重复选择相同的元素。有两种方法：

  • 方法一：将原数组排序，每层递归中，相邻的相同元素，只选择第一个（或只选择最后一个）
  • 方法二：是使用一个哈希表记录本轮递归过程中已经选择过的元素，不再重复选择，这种方法对空间复杂度的影响是 $O(n)$

解法一：下一个排列

略。

解法二：回溯遍历法

解法二使用排序或哈希表均可去重。这里以排序为例：将原数组排序，每层递归中，相邻的相同元素，只选择最后一个。

时间复杂度：不变，$O(n^n)$。
空间复杂度：不变，$O(n)$。

var res [][]int
var flag []bool

func permuteUnique(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
+	sort.Ints(nums) // 先排序
	res = [][]int{}
	flag = make([]bool, len(nums))
	dfs(nums, []int{})
	return res
}

func dfs(nums, cur []int) {
	if len(cur) == len(nums) {
		res = append(res, copyNums(cur))
		return
	}
	for i := 0; i < len(nums); i++ {
+		if i < len(nums)-1 && flag[i+1] == false && nums[i] == nums[i+1] { // 相同的元素，选择最后一个
+			continue
+		}
		if flag[i] == false {
			flag[i] = true
			cur = append(cur, nums[i])
			dfs(nums, cur)
			flag[i] = false
			cur = cur[:len(cur)-1]
		}
	}
}

解法三：回溯交换法

解法三只能使用哈希表去重，因为它会修改原数组的顺序。使用一个哈希表记录本轮递归过程中已经选择过的元素，不再重复选择。

时间复杂度：不变，$O(\sum_{k = 1}^{n}{A_n^k})$。
空间复杂度：从 $O(n)$ 变为 $O(n^2)$。

var res [][]int

func permuteUnique(nums []int) [][]int {
	if len(nums) == 0 {
		return nil
	}
+	sort.Ints(nums) // 先排序
	res = [][]int{}
	dfs(nums, 0)
	return res
}

func dfs(nums []int, start int) {
	if start == len(nums)-1 {
		res = append(res, copyNums(nums))
		return
	}
+	selected := map[int]bool{}
	for i := start; i < len(nums); i++ {
+		if _, ok := selected[nums[i]]; ok { // 已经选择过的就不再选择
+			continue
+		}
+		selected[nums[i]] = true
		nums[start], nums[i] = nums[i], nums[start]
		dfs(nums, start+1)
		nums[start], nums[i] = nums[i], nums[start]
	}
}

结语

本文发表在我的博客 https://imageslr.com/。我也会分享更多的题解，一起交流，共同进步！