aboutsummaryrefslogtreecommitdiff
path: root/permutation_sequence.py
blob: 96d8377d0a5b34d402035dc6437add45da0912c1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 60. Permutation Sequence
import math

"""
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 k'th permutation sequence
"""


class Solution(object):
    def getPermutation(self, n, k):
        nums = range(1, n + 1)
        permutation = ""
        k -= 1
        while n > 0:
            n -= 1
            idx, k = divmod(k, math.factorial(n))
            permutation += str(nums[idx])
            nums.remove(nums[idx])
        return permutation


if __name__ == "__main__":
    obj = Solution()
    print(obj.getPermutation(3, 3))  # expect: 213
    print(obj.getPermutation(4, 9))  # expect: 2314
    print(obj.getPermutation(3, 1))  # expect: 123