Share my Python solution with detailed explanation


  • 27
    D

    The idea is as follow:

    For permutations of n, the first (n-1)! permutations start with 1, next (n-1)! ones start with 2, ... and so on. And in each group of (n-1)! permutations, the first (n-2)! permutations start with the smallest remaining number, ...

    take n = 3 as an example, the first 2 (that is, (3-1)! ) permutations start with 1, next 2 start with 2 and last 2 start with 3. For the first 2 permutations (123 and 132), the 1st one (1!) starts with 2, which is the smallest remaining number (2 and 3). So we can use a loop to check the region that the sequence number falls in and get the starting digit. Then we adjust the sequence number and continue.

    import math
    class Solution:
        # @param {integer} n
        # @param {integer} k
        # @return {string}
        def getPermutation(self, n, k):
            numbers = range(1, n+1)
            permutation = ''
            k -= 1
            while n > 0:
                n -= 1
                # get the index of current digit
                index, k = divmod(k, math.factorial(n))
                permutation += str(numbers[index])
                # remove handled number
                numbers.remove(numbers[index])
    
            return permutation

  • 1
    Z

    You can move factorial outside of the loop and call it only once, given that n is decreasing by 1 every iteration.


  • 4
    T

    similar idea! may be a little faster, without extern lib.

    def getPermutation(self, n, k):
        elements = range(1, n+1)
        NN = reduce(operator.mul, elements) # n!
        k, result = (k-1) % NN, ''
        while len(elements) > 0:
            NN = NN / len(elements)
            i, k = k / NN, k % NN
            result += str(elements.pop(i))
        return result

  • 0
    H
    This post is deleted!

  • 0

    what is the runtime of you algorithm?
    is remove takes On time?


  • 0

    @tju_xu97 divmod is builtin function


  • 0
    T

    @Zura thank you!


  • 0

    Easy to understand

    class Solution(object):
        def getPermutation(self, n, k):
            nums = map(str,range(1,10))
            k -= 1
            factorial = [1] * n
            for i in range(1, n):
                factorial[i] = factorial[i - 1] * i
            res=[]
            for i in range(n):
                index = k / factorial[n - 1 - i]
                res.append(nums[index])
                nums.remove(nums[index])
                k = k % factorial[n - 1 - i]
            return ''.join(res)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.