Permutation Sequence

Question

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.

Tags

• Backtracking
• Maths

Thought

Reference: http://www.cnblogs.com/zuoyuan/p/3785530.html

Code

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        # http://www.cnblogs.com/zuoyuan/p/3785530.html
        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