60. Permutation Sequence

Loading...LeetCode

关于排列组合的题主要有三种类型：

1.生成所有的排列组合。

2.生成下一个排列组合。

3.生成排列号为k的排列组合（当前问题）。

如果生成 permutations 的顺序并不重要，可以使用 "交换 "回溯法( swap backtracking, 可见 46. Permutations )来解决第一个问题，并在 O(N*N!) 时间内生成所有 N! permutations。

不过，使用D.E.Knuth（见 31. Next Permutation）算法按 lexicographically 顺序生成 permutations 更好。该算法从前一个permutation 法生成新的 permutation，时间为 O(N) 。同样的算法可以用来解决上述第二个问题。

但上面两个算法都不适用于第三个问题，因为你将被要求在多项式时间内完成，而且并不知道前一个 permutation. 此时需要按照顺序生成所有的 permutation，再找到其中第k个。

在 78. Subsets 中，解法使用了二进制位掩码去映射长度为N的子集，其中ith 0表示“不存在元素编号i”，而ith 1表示“存在元素编号i”。对于 permutation 可以做同样的事情，利用 Factorial number system 对 permutation 进行映射。

Leetcode 官方solution 的图解就很不错：https://leetcode.co m/articles/permutation-sequence/

这个 discussion 也解释得挺简单的：https://leetcode.com/problems/permutation-sequence/discuss/696368/Detailed-Explanation-with-Example-Dry-Run-or-Clean-Code

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        factorials = [1]
        for i in range(1, n):
            # factorial 系统中，每一个位置代表的实际值 (n-1)!
            factorials.append(factorials[i - 1] * i)
        
        # 因为已经用过的元素需要去掉，需要生成一个 1~n 的有序数列
        nums = [str(i+1) for i in range(n)]
        
        k -= 1 # k是从1算起的，fit 进 [0, n!-1] 的话需要 remove 1
        
        # 根据factorials系统计算 k 代表的 permutation
        res = ''
        for i in range(n - 1, -1, -1):
            # 当前位(position)的表示值应该是 idx
            idx = k // factorials[i]
            # k减去当前位代表的真实值
            k -= idx * factorials[i]
            
            # 把表示值放进结果
            res += nums[idx]
            # 该数字已经用过，需要去掉
            nums.pop(idx)
        
        return res

简单示意下代码，以 n=3, k=3 为例：