LeetCode----Permutation Sequence

Permutation Sequence

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.

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

分析：

使用康托展开，直接生成第k个排列。了解原理请看：康托展开。

代码：

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        remains = k - 1
        div = []
        for i in range(n):
            a, remains = divmod(remains, self.getFactory(n - i - 1))
            div.append(a)
        res = ''
        seq = range(1, n + 1)
        for i in div:
            res += str(seq[i])
            del seq[i]
        return res

    def getFactory(self, n):
        if n in [0, 1]:
            return 1
        return reduce(lambda x, y: x*y, range(1, n + 1))