The set[1,2,3,…,n]contains a total ofn! unique permutations.
By listing and labeling all of the permutations in order,We get the following sequence (ie, forn= 3):
Givennandk, return thekthpermutation sequence.
I post two methods.. the first one is brute force. which is N! time.
the second one is linear time.
input fac = (n-1)!
k = k -1
1. get the value from the candidate sequences with fac and K
2. remove the value
3 decrease k with k%fac and fac = fac/i
## num, val, res visitdef backtrack(num, val, res, visit, k):if len(val) == len(num):res.append(val)return for i in range(len(num)):if visit[i] == False:visit[i] = Truebacktrack(num, val + [num[i]], res, visit, k)visit[i] = Falsenum = [1, 2, 3]val = []res = []visit = [False for i in range(len(num))]#print range(1,10)#backtrack(num, val, res, visit, 2)def getRes(n, k):num = range(1,10)fac = 1k -= 1res = []for i in range(1, n):fac *= ifor i in reversed(range(n)):res.append(str(num[k / fac]))num.remove(num[k / fac])if i != 0:k = k % facfac /= ireturn "".join(res)print getRes(3, 3)
，生活若剥去了理想梦想幻想，那生命便只是一堆空架子
