LeetCode#60 Permutation Sequence

Problem Definition:

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

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the k^th permutation sequence.

Note: Given n will be between 1 and 9 inclusive.

Solution:

还是Permutation. 试过用 Next Permutation 的算法，从第一个开始算k次，超时。

还是分析一下吧...

1._输入n，一共有n!种不同的Permutation;

2._看第一个字符：以‘1’作为第一个字符的Permutation一共有(n-1)!个，作为一组。同样，以‘2’、‘3’、...‘n’开头的串分别都有(n-1)！个。

　这样形成了总共 n x (n-1)!=n!个Permutation，令base=(n-1)!，表示当前每组中的个体数;

3._给定一个k，它将落在一个范围：(m-1)x( (n-1)! )<=k<=m x ( (n-1)! )，这里m是[1, n]间的一个数。

4._求出m，则 m-1 就是第一个字符在基本字符数组（这里就是nums=[1,2,3...n]）中的下标 i。

5._以上过程找到了输入(n, k)时输出的串的第一个字符，迭代以上过程，直到找到一个长度为 n的串。

每次迭代，k和base都会改变：

k=k-i*base, where base是本次迭代中，每个分组的个体数，最开始base是(n-1)!，然后下一次变为(n-2)!......

nums.pop( i )，即从nums中删去本次本选中的字符。

代码：

 1     # @param {integer} n
 2     # @param {integer} k
 3     # @return {string}
 4     def getPermutation(n, k):
 5         permu=range(1, n+1)
 6         res=''
 7         for _ in range(n):
 8             c,k=recur(permu, k)
 9             res+=str(c)
10         return res
11 
12     def recur(labels, k):
13         base=reduce(lambda x,y: x*y, range(1, len(labels)), 1)
14         i=1
15         while k>i*base:
16             i+=1
17         i-=1
18         c=labels[i]
19         
20         k-=base*i
21         labels.pop(i)
22         return [c, k]
23