forked from partho-maple/coding-interview-gym
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Permutations.py
46 lines (32 loc) · 1.3 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
# https://www.algoexpert.io/questions/Permutations
# Solution 1
# Upper Bound: O(n^2*n) time | O(n*n!) space
# Roughly: O(n*n!) time | O(n*n!) space
def ge_permutation(array):
permutations = []
permutation_helper(array, [], permutations)
return permutations
def permutation_helper(remaining_input_array, current_permutation, total_permutations):
if not len(remaining_input_array) and len(current_permutation):
total_permutations.append(current_permutation)
else:
for i in range(len(remaining_input_array)):
new_array = remaining_input_array[:i] + remaining_input_array[i + 1:]
new_permutation = current_permutation + [remaining_input_array[i]]
permutation_helper(new_array, new_permutation, total_permutations)
# Solution 2
# O(n*n!) time | O(n*n!) space
def ge_permutation(array):
permutations = []
permutation_helper(0, array, permutations)
return permutations
def permutation_helper(i, array, total_permutations):
if i == len(array) - 1:
total_permutations.append(array[:])
else:
for j in range(i, len(array)):
swap(array, i, j)
permutation_helper(i + 1, array, total_permutations)
swap(array, i, j)
def swap(array, i, j):
array[i], array[j] = array[j], array[i]