[60] Permutation Sequence

https://leetcode.com/problems/permutation-sequence/description/

• algorithms
• Medium (31.27%)
• Source Code: 60.permutation-sequence.py
• Total Accepted: 134.1K
• Total Submissions: 409.5K
• Testcase Example: '3\n3'

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:

"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.
Given k will be between 1 and n! inclusive.

Example 1:

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

Example 2:

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

class Solution(object):
    def getPermutation(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: str
        """
        from itertools import permutations

        pool = list(range(1, n+1))

        j = 0
        g = permutations(pool)
        while j < k:
            element = next(g)
            j += 1

        return ''.join([str(item) for item in element])
#
#
# s = Solution()
# print s.getPermutation(4, 9)
#