https://leetcode.com/problems/permutation-sequence/
参考：http://bangbingsyb.blogspot.hk/2014/11/leetcode-permutation-sequence.html
http://fisherlei.blogspot.hk/2013/04/leetcode-permutation-sequence-solution.html
思路： 分别计算第k个permutation的各个字母。
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
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)):#生成的数肯定是n位的，每一位逐个生成
curr = num[k/fac]
res += str(curr)
num.remove(curr)#因为确定了这个数之后，后面不会有这个数出现了。注意这里是用remove，list的ind也变了
if i !=0:
k %= fac
fac /= i
return res自己重写code
class Solution(object):
def getPermutation(self, n, k):
"""
:type n: int
:type k: int
:rtype: str
"""
fac = 1
for i in xrange(n-1):
fac *= i+1
tmp = [i+1 for i in xrange(n)]
ans = ''
k -= 1#这里先减去1
for i in xrange(n-1, -1, -1):
j = k/fac
ans += str(tmp[j])
tmp.remove(tmp[j])#这里要是remove(tmp[j]),不是remove(j)
if i != 0:#这里要分清楚最后一个数，如果不是最后一个数。最后一个数就不用再除了。
k %= fac
fac /=i
return ans