1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# 60. Permutation Sequence
import math
"""
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 k'th permutation sequence
"""
class Solution(object):
def getPermutation(self, n, k):
nums = range(1, n + 1)
permutation = ""
k -= 1
while n > 0:
n -= 1
idx, k = divmod(k, math.factorial(n))
permutation += str(nums[idx])
nums.remove(nums[idx])
return permutation
if __name__ == "__main__":
obj = Solution()
print(obj.getPermutation(3, 3)) # expect: 213
print(obj.getPermutation(4, 9)) # expect: 2314
print(obj.getPermutation(3, 1)) # expect: 123
|