-
Notifications
You must be signed in to change notification settings - Fork 24
/
46 - Permutations.py
70 lines (67 loc) · 2.35 KB
/
46 - Permutations.py
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# Solution 1: Recursive solution by swapping
# Ex. [1,2,3]
# We should make the following recursive calls
# [1] + perm(2,3)
# [2] + perm(1,3)
# [3] + perm(1,2)
# Runtime: O(n*n!)
class Solution(object):
def recursivePermute(self, nums, perms, perm):
if len(nums) == 0:
perms.append(perm)
return
for i in range(0,len(nums)):
tmp = nums[0]
nums[0] = nums[i]
nums[i] = tmp
self.recursivePermute(nums[1:],perms,perm + [nums[0]])
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
perms = []
self.recursivePermute(nums,perms,[])
return perms
# Solution 2: Iterative solution using list concatentation, add
# an element to every possible position in every existing permutation.
# Runtime: O(n*n!) since there are n! permutations and it takes O(n) time to build each one
# This runs slightly faster than the recursive solution due to less overhead.
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
# Start with a permutation of just 1 element
perms = [[nums[0]]]
# For every remaining element, add it to every existing permutation in every possible index
# ex. [1,2,3]
# perms = [1]
# Add 2 to [1] in every possible index (before and after)
# perms = [2,1], [1,2]
# Add 3 to [2,1] and [1,2] in every possible index
# perms = [3,2,1], [2,3,1], [2,1,3], [3,1,2], [1,3,2], [1,2,3]
for i in range(1,len(nums)):
num = nums[i]
for j in range(len(perms)):
perm = perms[j]
for k in range(len(perm)):
perms += [perm[0:k] + [num] + perm[k:]]
perm.append(num) # add it to the end of the existing perm
return perms
# Solution 3: Slightly more concise version of #2
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
perms = [[]]
for num in nums:
newPerms = []
for perm in perms:
for k in range(len(perm)+1):
newPerms.append(perm[0:k] + [num] + perm[k:])
perms = newPerms
return perms