算法题--给定数字n, 求第k个全排列

image.png

0. 链接

题目链接

1. 题目

The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

2. 思路1：递归

[1,2,3,4]的全排列可以写出:

1 --> (1, 2, 3, 4)
2 --> (1, 2, 4, 3)
3 --> (1, 3, 2, 4)
4 --> (1, 3, 4, 2)
5 --> (1, 4, 2, 3)
6 --> (1, 4, 3, 2)
7 --> (2, 1, 3, 4)
8 --> (2, 1, 4, 3)
9 --> (2, 3, 1, 4)
10 --> (2, 3, 4, 1)
11 --> (2, 4, 1, 3)
12 --> (2, 4, 3, 1)
13 --> (3, 1, 2, 4)
14 --> (3, 1, 4, 2)
15 --> (3, 2, 1, 4)
16 --> (3, 2, 4, 1)
17 --> (3, 4, 1, 2)
18 --> (3, 4, 2, 1)
19 --> (4, 1, 2, 3)
20 --> (4, 1, 3, 2)
21 --> (4, 2, 1, 3)
22 --> (4, 2, 3, 1)
23 --> (4, 3, 1, 2)
24 --> (4, 3, 2, 1)

从中可以看出

• 以1, 2, 3, 4开头的, 各有3!=6个
• 以1开头的6个排列里，剩余值以2开头的有2!=2个
• 在1,2开头的2个排列里, 剩余值以3开头的有1!=1个
• 在以1,2,3开头的排列里, 剩余值以4开头的有0!=1个

可见，满足典型的递归规律, 详细如下所示:

• 对于原问题, 即给定数组[1,2,3,4]，要求出第9个排列
  可以从左到右依次确定每个数字
• 显然第1个数字, 可以通过(9 - 1) // 3! = 1得到第一个数字在数组[1,2,3,4]中的下标，这样得到数字2
• 第1个数字确定后, 问题转化为子问题，即给定数组[1,3,4], 要求出第9 % 3!=3个排列的问题

3. 代码

# coding:utf8
from typing import List


class Solution:
    def find(self, nums: List[int], k: int, multi: int, results: List[str]):
        if len(nums) == 0:
            return
        if len(nums) == 1:
            results.append(chr(ord('0') + nums[0]))
            nums.pop(0)
            return
        else:
            head_idx = (k - 1) // multi
            results.append(chr(ord('0') + nums.pop(head_idx)))
            k = k % multi
            multi = multi // len(nums)
            self.find(nums, k, multi, results)

    def getPermutation(self, n: int, k: int) -> str:
        multi = 1
        for i in range(1, n):
            multi *= i

        nums = list(range(1, n + 1))
        results = list()
        self.find(nums, k, multi, results)
        return ''.join(results)


solution = Solution()
print(solution.getPermutation(3, 3))
print(solution.getPermutation(4, 9))

输出结果

213
2314

4. 结果

image.png