# 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