60. Permutation Sequence

import math
class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        #the nth number rotate every (n-1)! times 
        res=''
        num=[i for i in xrange(1,10)]
        k=k-1
        fact=math.factorial(n-1)
        
        for i in reversed(xrange(n)):
            out=num[k/fact]
            res+=str(out)
            num.remove(out)
            if i>0:
                k%=fact
                fact/=i
        return res