def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        # let permutations with first identical num be a block
        # target in (k - 1) / (n - 1)! block
        remain = range(1, n + 1)
        if k <= 1:
            return ''.join(str(t) for t in remain)
        total = 1
        for num in remain[:-1]:
            total *= num
        res = self.do_getPermutation(remain, total, n - 1, k - 1)
        return ''.join(str(t) for t in res)

        :type n: int
        :type k: int
        :rtype: str
        
python/060_Permutation_Sequence.py