60. permutation sequence leetcode python

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 (ie, for n = 3):

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation 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 visit
def 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] = True
			backtrack(num, val + [num[i]], res, visit, k)
			visit[i] = False




num = [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 = 1
	k -= 1
	res = []
	for i in range(1, n):
		fac *= i
	for i in reversed(range(n)):
		res.append(str(num[k / fac]))
		num.remove(num[k / fac])
		if i != 0:
			k = k % fac
			fac /= i
	return "".join(res)




print getRes(3, 3)

60. permutation sequence leetcode python

原文：http://blog.csdn.net/hyperbolechi/article/details/44664061