Permutation Sequence

题目描述

Given n and k, return the kth permutation sequence.

解题方法

因为是permutation，所以肯定会有n位数字

• 选定了第1位，后面的有(n-1)!种组合
• 选定了第2位，后面有(n-2)!种组合
• 。。。。

所以根据这个规律，我们可以计算出每一位应该用什么数。

要注意的是，用完了这个数后，我们要删除它防止再用，所以可以用一个array来 存储可用的数。

因为permutation的排列是从1开始的，而不是0开始的，所以我们会遇到问题： 比如第(n-1)!个数，它的第一位应该选择的是最小的数字，但是 / (n-1)!的结果 是1，会选择second smallest num available。

为了便于计算，我们应该将k减去1，变成0 based的，这样更好计算。

Solution

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        result = ""
        nums = [] # construct a array to store nums that can be used
        factorial = 1

        for i in range(1, n+1):
            nums.append(i)
            factorial *= i

        k -= 1 # become 0-based
        for i in range(n, 0, -1):
            factorial /= i
            index = k / factorial
            result += str(nums[index])
            del nums[index]
            k %= factorial

        return result

Reference