卖萌的弱渣

I am stupid, I am hungry.

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 (ie, for n = 3):

1
2
3
4
5
6

"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.

Solution

  • The first digit is k/(n-1)!, then let k = k % (n-1)! and remove this digit from num.
  • The second digit is k/(n-2)!, then let k = k % (n-2)! and remove this digit from num and so on.
(Permutation-Sequence.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
   def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        #Generate the sequence
        k = k-1
        nums = [i for i in range(1,n+1)]
        factorial = 1
        # calculate (n-1)!
        for i in range(1,n):
            factorial *= i
        ret = ""
        for i in range(n-1,-1,-1):
            ret += str(nums[k/factorial])
            nums.remove(nums[k/factorial])
            if i!=0:
                k = k%factorial
                factorial = factorial/i
        return ret