https://leetcode.com/problems/permutation-sequence/
Permutation Sequence
The set [1,2,3,…,<i>n</i>] 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):
"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.
Code
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
res = ""
arr = range(1, n+1)
k = k-1
for i in xrange(n-1, -1, -1):
idx, k = divmod(k, math.factorial(i))
res += str(arr.pop(idx))
return res
Idea
Always try to determine which is the next character to append.
For example,
n=3, we have 6 permutations in total:
123 132 213 231 312 321
If k=3, we know we should return 213. We should first determine we need to append “2”. How to determine that? we know that there are (n-1)! permutations that start with “1”, “2” and “3” each. So the integer quotient of (k-1)/(n-1)! represents the index (0-based) of the number in the original array (1,2,3).
You keep doing this iteratively to get the final result.