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"

Difficulty: interview

Starter code:

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        

Solutions:
class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         nums = list("123456789")
         k -= 1
         factor = 1
         for i in range(1, n):
             factor *= i
         res = []
         for i in reversed(list(range(n))):
             res.append(nums[k//factor])
             nums.remove(nums[k//factor])
             if i:
                 k %= factor
                 factor //= i
         return "".join(res)


class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         def factorial(n):
             if n == 0:
                 return 1
             m = 1
             while n>0:
                 m = m*n
                 n -= 1
             return m
         ans = ""
         digits = [i+1 for i in range(n)]
         print(("digits: ",digits))
         total = factorial(n)
         while(len(digits)>0):
             rem = k%factorial(n-1)
             digit = digits[(k//factorial(n-1) + 1*(rem>0)) -1]
             ans+=str(digit)
             digits.remove(digit)
             k = rem
             n -= 1
         return ans
             
             
 


class Solution:
     import math
     
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         a = 0
         options = ""
         for i in range(n):
             options += str(i + 1)
         ans = ""
         while n > 0:
             x = math.factorial(n - 1)
             while k > x:
                 k -= x
                 a += 1
             ans += options[a]
             options = options[:a] + options[a + 1:]
             a = 0
             n -= 1
         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 
         


class Solution:
     def getPermutation(self, n, k):
         """
         Input:
             n:  int
             k:  int
         Output:
             str
         """
         return self.__getPerm(set(range(1, n+1)), k)
 
 
 
     def __getPerm(self, set_n, k):
         """
         Input:
             set_n:  set:    set of available number
             k:  int:        k-th permuation
         Output:
             str
         """
         if not set_n:
             return ''
 
         arr_n = sorted(set_n)
         n = len(arr_n)
         i = 0
         fac = 1     # i!
 
         while i+1 < n:
             i += 1
             fac *= i
         
         # fac = (n-1)!
         i_digit = (k-1)//fac
         k = k - i_digit*fac
         digit = arr_n[i_digit]
 
         set_n.remove(digit)
         return str(digit) + self.__getPerm(set_n, k)


class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         nums = [i + 1 for i in range(0, n)]
         def nextnum(nn):
             cnt = 0
             for i in range(0, len(nums)):
                 if nums[i] == 0:
                     continue
                 cnt += 1
                 if cnt == nn:
                     ret = nums[i]
                     nums[i] = 0
                     return ret
         
         facts = [1]
         for i in range(1, n+2):
             facts.append(facts[i-1] * i)
         perm = []
         while (n > 1):
             nk = (k - 1) // facts[n-1] + 1
             rk = (k - 1) % facts[n-1] + 1
             perm.append(nextnum(nk))
             k = rk
             n -= 1
         perm.append(nextnum(k))
         return "".join([str(x) for x in perm])


class Solution:
     def factorial(self, n):
         if n <= 1:
             return 1
         return self.factorial(n-1) * n
     
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         r = ''
         nums = [i+1 for i in range(n)]
         m = n 
         while m:
             np = self.factorial(m-1)
             i = (k-1)//np
             k -= i*np
             r += str(nums[i])
             del nums[i]
             m = len(nums)
         return r
         


class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         
         import math
         if k > math.factorial(n):
             return None
         else:
             nums = [str(i) for i in range(1,n+1)]
             ans = ''
             while k % math.factorial(len(nums)) != 0:
                 i = math.ceil(k / math.factorial(len(nums)-1))
                 k %= math.factorial(len(nums)-1)
                 ans += nums[i-1]
                 nums.pop(i-1)
             ans += ''.join(nums[::-1])
             return ans
                     


class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         ans = ""
         nums = list(range(1,n+1))
         m = self.factorial(n-1)
         
         while len(nums)>1:
             print("n=",n, ", k=",k, " m=", m)
             remainer = k % m
             if remainer==0:
                 remainer = m
             index = (k-remainer) // m
             print(index)
             ans += str(nums[index])
             nums.remove(nums[index])
             k = remainer
             n -= 1
             m = m // n
             
         ans += str(nums[0])
         return ans
     
     def factorial(self, n):
         if n==1 or n==0:
             return 1
         else:
             return n*self.factorial(n-1)

class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         ret = ""
         strs = [str(_) for _ in range(1, n + 1)]
         divisor = 1
         for i in range(1, n + 1): 
             divisor *= i
         total_index = k - 1
         while len(ret) < n:
             divisor //= len(strs)
             index = total_index // divisor
             total_index %= divisor
             ret += strs[index]
             strs.pop(index)
         return ret

class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         numbers = list(range(1, n+1))
         permutation = ''
         k -= 1
         
         while numbers:
             n -= 1
             index, k = divmod(k, math.factorial(n))
             '''print(index)
             print(numbers)'''
             permutation += str(numbers[index])
             numbers.remove(numbers[index])
             
         return permutation 

class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         string = ""
         selection = [i for i in range(n + 1)]
         while n > 0: 
             quo, temp = divmod(k - 1, self.factorial(n - 1))
             string += str(selection[quo + 1])
             selection.remove(selection[quo + 1])
             n -= 1
             k = temp + 1
         return string
         
         
     def factorial(self, n): 
         if not n: return 1
         product = 1
         for i in range(1, n + 1): 
             product *= i 
         return product

class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
 
         def fn(x, y):
             return x*y
 
         import functools
 
         nums = list(range(1, n+1))
         nn = functools.reduce(fn, nums)
         out = ""
         k = k-1
         
         while n > 1:
             nn = nn // n
             
             idx, k = k//nn, k%nn 
             out = out + str(nums[idx])
             nums.remove(nums[idx])
 
             n = n - 1
 
         out = out + str(nums[0])
         return out        
 


class Solution:
     def getPermutation(self, n, k):
         """
         :type n: int
         :type k: int
         :rtype: str
         """
         numbers = [x for x in range(1, n+1)] 
 
         factorial = [1]* n
         for i in range(1,n):
             factorial[i] = factorial[i-1]*(i)
 
         result = []
 
         for i in range(1, n+1):
             index = (k-1)//factorial[n-i]
             k=k%factorial[n-i]
 
             result.append(numbers[index])
             numbers.remove(numbers[index])
         return ''.join(map(str,result))