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):

"123"
"132"
"213"
"231"
"312"
"321"

Given n and k, return the kth permutation sequence.

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

解题方法

这个也是一个排列问题，根据排列问题的规律和总结， n个数会有n!个排列，对于第一位的数字有n种选法，之后的n-1位 的排列有(n-1)!种，根据这几条规律我们就可以确定第一位数字，后面的数字也同理求得。

同一个数字不能重复用，所以我们应该用一个array来保存用过的数或者未用过的数，为了方便选择下一个number，我们保存 未用过的数，通过对应的index找到下一个该用的数，同时要记得将用过的数删除。

k应该减去1来计算，比如n=3，

1. "123"
2. "132"

他们/ (3-1)!的结果是不一样的，但是他们前面的数都应该是1，对于每一个(n-1)!的组合，他们的结果应该一样，所以直接减去1 变为0-based比较好计算

注意点

• 用一个array保存未用的数
• 记得删去用过的数
• k要减去1更方便计算

Solution

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        if not n:
            return ""
        result = ""
        product = 1
        nums = [] #use an array to keep all remaining potential numbers
        for i in range(1, n+1):
            nums.append(i)
            product *= i
        if k > product:
            return ""
        k = k - 1

        for j in range(n, 0, -1):
            product /= j
            index = k / product
            result += str(nums[index])
            del nums[index] #should delete from numbers array
            k = k % product

        return result

Reference