[Leetcode][python]Permutation Sequence/k番目の配列

テーマの大意
[1,2,3,...n]のすべての数字からなるシーケンスのk番目に大きいものを見つけた.
注意点:nは1-9の数値です.
問題を解く構想.
ソース:http://www.cnblogs.com/zuoyuan/p/3785530.html私が採用した方法はk番目のPermutationを計算することです.n=6,k=400が最初に1位を計算し,1位が6であると仮定すると,少なくとも5位である!*5+1個が並んでいます.これは1位が1/2/3/4/5のとき、5があったからです.このため、1位が6の場合、少なくとも5位です!*5+1個の配列(この配列は612345).5! * 5+1=601>kなので、1位は6.1位が4になるまで1つずつ列挙します.この場合、4 xxxxは少なくとも5位です.*3+1=361配列.そして2位を計算し、1位を計算するときとの違いは、46 xxxxが少なくとも4位であることです!*4+1=97個の配列で、6より小さいのは5/3/2/1しかないからです.最後に2番目のビットが2であることを計算することができる.
コード#コード#
遡る
この問題の標準は構造を遡るので,私もできるだけ標準的に書く.

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        curr = []
        self.result = ''
        for i in range(1, n+1):
            curr.append(i) 
        self.getPermutationHelper(n, k, curr)
        return self.result
    def getPermutationHelper(self, index, rest, curr):
        # print index, rest, '  str：', curr
        if index == 0:
            return 
        for i in range(index-1, -1, -1):
            temp = math.factorial(index-1)
            # print temp, i, rest - (temp * i + 1)
            if rest - (temp * i + 1) >= 0:
                self.result += str(curr[i])
                curr.pop(i)
                # print(curr)
                self.getPermutationHelper(index-1, rest - (temp * i), curr)
                break

オンライン解法
実は考え方は同じで、私の効率は低いです.

class Solution:

    def getPermutation(self, n, k):
        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

まとめ
遡及には基本構造がある