-
Notifications
You must be signed in to change notification settings - Fork 2
/
permutations.py
49 lines (37 loc) · 1.18 KB
/
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
"""
This implementation demonstrates how
to generate all the permutations of
a given set of integers.
Example:
For following array: [1, 2, 3]
The output would be:
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1],
[3, 1, 2], [3, 2, 1]]
Let n be the size of the array.
Time complexity: O(n*n!)
Space complexity: O(n*n!)
"""
def find_permutations(array):
permutations = []
generate_permutations(0, array, permutations)
return permutations
def generate_permutations(idx, array, permutations):
if idx == len(array) - 1:
permutations.append(array[:]) # add a copy of array to output
else:
for j in range(idx, len(array)):
swap(array, idx, j) # swap idxth elem with every other elem
generate_permutations(idx+1, array, permutations)
swap(array, j, idx) # backtrack
def swap(array, i, j):
array[i], array[j] = array[j], array[i]
# Below outputs:
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
print(find_permutations([1, 2, 3]))
"""
# Another solution:
import itertools
# Below output:
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
print(list(itertools.permutations([1, 2, 3])))
"""