首页 > 代码库 > [leetcode]Permutation Sequence @ Python
[leetcode]Permutation Sequence @ Python
原题地址：https://oj.leetcode.com/submissions/detail/5341904/
题意：
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 kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.
解题思路：刚开始用dfs，但一直TLE。貌似用java和c++写dfs可以过，看来python确实慢啊。只能采用一种更巧妙的思路了。
其实本题数据不大，n最多为9，9! = 362880，枚举应该能够通过（我没试验）。
我采用的方法是计算第k个Permutation。
假设n = 6，k = 400
先计算第一位，
第一位为6，那么它最少也是第5! * 5 + 1个排列，这是因为第一位为1/2/3/4/5时，都有5!个排列，因此第一位为6时，至少是第5! * 5 + 1个排列（这个排列为612345）。
5! * 5 + 1 = 601 > k，所以第一位不可能是6.
一个一个地枚举，直到第一位为4时才行，这时，4xxxxx至少为第5! * 3 + 1 = 361个排列。
然后计算第二位，
与计算第一位时的区别在于，46xxxx至少为第4! * 4 + 1 = 97个排列，这是因为比6小的只有5/3/2/1了。
最后可以计算出第二位为2。
最终得出第400个排列为425361。
代码：
class Solution: # @return a string # def dfs(self, n, k, string, stringlist): # if len(stringlist) == n: # Solution.count += 1 # if Solution.count == k: # print stringlist # return # for i in range(len(string)): # self.dfs(n, k, string[:i]+string[i+1:], stringlist+string[i]) # def getPermutation(self, n, k): # string = ‘‘ # for i in range(n): string += str(i+1) # Solution.count = 0 # self.dfs(n, k, string, ‘‘) def getPermutation(self, n, k): res = ‘‘ k -= 1 fac = 1 for i in range(1, n): fac *= i num = [1, 2, 3, 4, 5, 6, 7, 8, 9] for i in reversed(range(n)): curr = num[k/fac] res += str(curr) num.remove(curr) if i !=0: k %= fac fac /= i return res