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"
Example 2:
Input: n = 4, k = 9
Output: "2314"
class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         import math
         nums = list(range(1, n+1))
         ans = ''
         
         k = k - 1 #make sure the divmod result fail in [0, n-1] instead of [1, n]
         while n > 0:
             n = n - 1
             index, k = divmod(k, math.factorial(n))
             ans = ans + str(nums[index])
             nums.remove(nums[index])
             
         return ans 
         

class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         import math
         nums = list(range(1, n+1))
         ans = ''
         
         k = k - 1 #make sure the divmod result fail in [0, n-1] instead of [1, n]
         while n > 0:
             n = n - 1
             index, k = divmod(k, math.factorial(n))
             ans = ans + str(nums[index])
             nums.remove(nums[index])
             
         return ans 
         
