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"

Source: leetcode | Difficulty: MEDIUM
Tags: Mathematics

Complete search

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

Solutions:
class Solution:

	def getPermutation(self, n, k):
		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):

		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):
		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):
		import math
		nums = list(range(1, n + 1))
		ans = ''
		k = k - 1
		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):
		return self.__getPerm(set(range(1, n + 1)), k)

	def __getPerm(self, set_n, k):
		if not set_n:
			return ''
		arr_n = sorted(set_n)
		n = len(arr_n)
		i = 0
		fac = 1
		while i + 1 < n:
			i += 1
			fac *= i
		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):
		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):
		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):
		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):
		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):
		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):
		numbers = list(range(1, n + 1))
		permutation = ''
		k -= 1
		while numbers:
			n -= 1
			(index, k) = divmod(k, math.factorial(n))
			permutation += str(numbers[index])
			numbers.remove(numbers[index])
		return permutation


class Solution:

	def getPermutation(self, n, k):
		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):

		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):
		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))