60-permutation-sequence

Try it on leetcode

Description

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 for n = 3:

1. "123"
2. "132"
3. "213"
4. "231"
5. "312"
6. "321"

Given n and k, return the kth permutation sequence.

 

Example 1:

Input: n = 3, k = 3
Output: "213"

Example 2:

Input: n = 4, k = 9
Output: "2314"

Example 3:

Input: n = 3, k = 1
Output: "123"

 

Constraints:

• 1 <= n <= 9
• 1 <= k <= n!

Solution(Python)

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        return self.optimal(n, k)

    # Time Complexity: O(n!)
    # Space Complexity: O(n)
    def bruteforce(self, n: int, k: int) -> str:

        res = []
        nums = [i for i in range(1, n + 1)]
        times = reduce(lambda x, y: x * y, nums)
        res.append(nums[:])
        for _ in range(1, times + 1):
            nums[:] = self.nextPermutation(nums)
            res.append(nums[:])
        return "".join(map(str, res[k - 1]))

    def nextPermutation(self, nums: List[int]) -> List[int]:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = n - 2

        while i >= 0 and nums[i + 1] <= nums[i]:
            i -= 1

        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1

            nums[j], nums[i] = nums[i], nums[j]

        s = i + 1
        e = n - 1

        while s < e:
            nums[s], nums[e] = nums[e], nums[s]
            s += 1
            e -= 1
        return nums

    # Time Complexity: O(n)
    # Space Complexity: O(n)
    # there are n! possibilties which means MSB index will be one of n numbers
    # which is n!/n = n-1!  in ascending order
    # so k/(n-1)! gives index of MSB k updates to k%(n-1)!
    # now for next MSB do k /(n-2)! gives index of next MSB and k updates to k%(n-2)!
    # do this until n !=0
    def optimal(self, n: int, k: int) -> str:
        # create nums array
        nums = [i for i in range(1, n + 1)]
        # create set from nums
        s = set(nums)

        # update k tozero indexbased
        k -= 1
        ans = ""

        fact = [1] * (n + 1)

        for i in range(1, n + 1):
            fact[i] = i * fact[i - 1]

        while n > 0:
            nums[:] = list(s)
            n -= 1
            # calculate index by k/(n-1)! k= k%(n-1)!
            index, k = divmod(k, fact[n])
            ans += str(nums[index])
            s.remove(nums[index])
        # remove that from sand append to ans
        return ans