FilesExpand file tree

 master

/

permutation-sequence.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

42 lines (37 loc) · 950 Bytes

 master

/

permutation-sequence.py

Copy path

Top

File metadata and controls

• Code
• Blame

42 lines (37 loc) · 950 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

30

31

32

33

34

35

36

37

38

39

40

41

42

# Time: O(n^2)

# Space: O(n)

# 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 (ie, 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.

import math

# Cantor ordering solution

class Solution(object):

def getPermutation(self, n, k):

"""

:type n: int

:type k: int

:rtype: str

"""

seq, k, fact = "", k - 1, math.factorial(n - 1)

perm = [i for i in xrange(1, n + 1)]

for i in reversed(xrange(n)):

curr = perm[k / fact]

seq += str(curr)

perm.remove(curr)

if i > 0:

k %= fact

fact /= i

return seq

if __name__ == "__main__":

print Solution().getPermutation(3, 2)