# 60. Permutation Sequence

{% embed url="<https://leetcode.com/problems/permutation-sequence/>" %}

> 关于排列组合的题主要有三种类型：
>
> 1.生成所有的排列组合。
>
> 2.生成下一个排列组合。
>
> 3.生成排列号为k的排列组合（当前问题）。

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

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

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

在 [78. Subsets](https://leetcode.com/articles/subsets/) 中，解法使用了二进制位掩码去映射长度为N的子集，其中ith 0表示“不存在元素编号i”，而ith 1表示“存在元素编号i”。对于 permutation  可以做同样的事情，利用 [Factorial number system](https://en.wikipedia.org/wiki/Factorial_number_system) 对 permutation 进行映射。

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

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

```python
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 为例：

![](https://1821609058-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M74fKaD-4PpYzUZfdEf%2F-MAIiUlwTChyQ_l_0Rqi%2F-MAIzQm5C5v2NzJnxf4G%2Fimage.png?alt=media\&token=d488b99e-759b-44d1-b841-3b59a87f241b)
