[Leetcode problems]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:
"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"

We don’t have to list all permutations since we are only interested in the k^{th} one. An optimized approach is based on the observations that,

  • The leftmost digit groups permutations in orders, i.e., when n = 3, 2xx is always larger than 1xx.
  • With different left-most digits, there arefactorial(len(number)-1) in each group.

Therefore, to find the k-th permutation, we can construct it from left to right. Take n=4,k=9 as an example:

  1. The first digit – n=4,k=9
    There are 4 groups of numbers with different leftmost digits: 1xxx, 2xxx, 3xxx, 4xxx, and each of them hasfactorial(4-1) items. Since k=9, we would skip 1xxx, so the 9^{th} permutation is 2xxx, and the task is to find the (9-factorial(n-1))-th=3^{rd} permutation in 2xxx.
  2. The second digit – n=3,k=3
    There are 3 groups of numbers with different ‘leftmost’ digits: 21xx, 23xx, 24xx. Note that we’ve fixed the first digit, so we are actually talking about the second digit. Each group has math.factorial(3-1) items and we are looking for the 3^{rd} one, therefore it would be in 23xx. Now the tasks is to find the (3-factorial(n-1))=1^{st} one in 23xx.
  3. The third digit – n=2,k=1 – 231x
  4. The fourth digit – 2314
    def getPermutation(self, n: int, k: int) -> str:
        nums = [str(i) for i in range(1,n+1)]
        ret = ''
        i = 0
        while n > 0:
            if k > math.factorial(n-1):
                i += 1
                k -= math.factorial(n-1)
            else:
                digit = str(nums.pop(i))
                n -= 1
                i = 0
                ret += digit
        return ret

Or, we can use divisions instead of subtractions in each iteration.

    def getPermutation(self, n: int, k: int) -> str:
        nums = [str(i) for i in range(1,n+1)]
        ret = ''
        while nums:
            remain = math.factorial(len(nums)-1)
            ret += nums.pop((k-1) // remain)
            k = k%remain if remain else remain
        return ret
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments