60. Permutation Sequence

2019-05-10

60. Permutation Sequence

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:

  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"

Given _n_ and _k_, return the _k_th permutation sequence.

Note:

  • Given _n_ will be between 1 and 9 inclusive.
  • Given _k_ will be between 1 and _n_! inclusive.

Example 1:

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

Example 2:

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

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        import math
        numbers = range(1, n+1)
        permutation = ''
        k -= 1
        while n > 0:
            n -= 1
            # get the index of current digit
            index, k = divmod(k, math.factorial(n))  # 阶乘y
            permutation += str(numbers[index])
            # remove handled number
            numbers.remove(numbers[index])

        return permutation
-->