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"
My code:
import numpy as np
class Solution:
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
str1=""
self.n=n
remove_list=[]
str1=self.find_str(str1,remove_list,n,k)
return str1
def find_str(self,str1,remove_list,n,k):
if len(str1)==self.n:
return str1
#print('length of remove list %d'%(len(remove_list)))
#print(self.n)
if len(remove_list)==self.n-1:
#Add the remained 1
for i in range(1,self.n+1):
if i not in remove_list:
str1=str1+str(i)
#print(str1)
return str1
possible=np.math.factorial(n-1)
check_index=int(np.floor(k/possible))
if k%possible==0:
check_index=check_index-1
print('check index %d, possible %d'%(check_index,possible))
count=0
for item in range(1,self.n+1):
print(item)
if item not in remove_list:
if check_index==count:
number=item
break
count+=1
remove_list.append(number)
str1=str1+str(number)
k=k-(check_index)*possible
#print(str1)
#print(k)
return self.find_str(str1,remove_list,n-1,k)
Solution: https://leetcode.com/problems/permutation-sequence/