# [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 