The set`[1,2,3,...,`

contains a total ofn]n! unique permutations. By listing and labeling all of the permutations in order, we get the following sequence forn= 3:`"123";"132"`

;`"213"`

;`"231"`

;`"312"`

;`"321"`

Givennandk, return thek^{t}^{h}permutation sequence.Note:Givennwill be between 1 and 9 inclusive. Givenkwill be between 1 andn! inclusive.Example 1:Input:n = 3, k = 3Output:"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 are
`factorial(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:

- 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 has`factorial(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. - 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. - The third digit – n=2,k=1 – 231x
- 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
```