Permutations refer to all possible arrangements of elements within a sequence, where the order of elements matters. Permutations can be generated for a list, tuple, or any iterable object.
Python provides several ways to work with permutations.
Let's explore the concept of permutations using examples.
Solution 1: Using recursion
You can implement your recursive function as follows
# upper bound: O(n^2*n!) time | O(n*n!) space
# roughly: O(n*n!) time | O(n*n!) space
def getPermutations(array):
permutations=[]
permutationsHelper(array, [], permutations)
return permutations
def permutationsHelper(array, currentPermutation, permutations):
if not len(array) and len(currentPermutation):
permutations.append(currentPermutation)
else:
for i in range(len(array)):
newArray =array[:i]+array[i+1:]
newPermutation = currentPermutation + [array[i]]
permutationsHelper(newArray, newPermutation, permutations)
print(f"permutations:: {getPermutations([1,2,3])}")
The getPermutations function is the entry point. It initializes an empty list called permutations, then calls the permutationsHelper function with the original array, an empty permutation list, and the permutations list.
The permutationsHelper function generates permutations recursively. It takes three parameters: the original array, the current permutation being built, and the list of permutations.
permutationsHelper function
If the length of the array is 0 and the length of the current permutation is not 0, it means that a permutation is complete, so the current permutation is appended to the list of permutations.
If the array is not empty, it iterates through each element of the array. As a result, it creates a new array excluding the current element (array[:i] + array[i+1:]) and a new permutation by adding the current element to the existing permutation (currentPermutation + [array[i]]).
Subsequently, it recursively calls itself with the new array and new permutation.
This process continues recursively until all permutations are generated.
One key thing to note here is the use of slicing to create new arrays without the current element, and the use of recursion to explore all possible permutations.
The final list of permutations contains all the permutations of the input array.
Time Complexity
Exploration of Permutations
In the permutationsHelper() function, for each element in the input array, we perform the following operations:
- Create a new array by excluding the current element (array[:i] + array[i+1:]), which takes O(n) time.
- Create a new permutation by appending the current element to the current permutation, which takes O(1) time.
- Recursively call permutationsHelper() with the new array and permutation.
The number of recursive calls made by permutationsHelper() depends on the number of elements in the array and the depth of recursion. Since we explore all possible permutations, the total number of recursive calls is O(n!).
For each recursive call, creating the new array and new permutation both take O(n) time. Therefore, the overall time complexity of the solution is O(n×n!).
Space Complexity
Recursive Call Stack
The space complexity due to the recursive call stack is determined by the maximum depth of recursion, which is equal to the length of the input array n. Therefore, the space complexity due to the call stack is O(n).
Permutations List
The space required to store all permutations depends on the number of permutations generated. Since there are n! permutations of an array of length n, the space complexity for storing permutations is O(n!×n) (considering the average length of each permutation).
Temporary Storage
During the recursion, some additional space is required for maintaining the current permutation and the new array in each recursive call. This temporary space is also O(n) since the length of the permutation and the array is at most n.
Total Space Complexity
The overall space complexity of the solution is O(n+n!×n), which simplifies to O(n!×n) as n! dominates when n is large.
Solution 2: Alternative Approach
Here's a variation of the solution above.
# O(n*n!) time | O(n*n!) space
def get_permutations(array):
permutations =[]
permutations_helper(0, array, permutations)
return permutations
def permutations_helper(i, array, permutations):
if i == len(array) -1:
permutations.append(array[:])
else:
for j in range(i, len(array)):
swap(array, i, j)
permutations_helper(i+1, array, permutations)
swap(array, i, j)
def swap(array, i, j):
array[i], array[j] = array[j], array[i]
print(f"optimized permutations:: {get_permutations([1,2,3])}")
Time Complexity
The permutations_helper() function explores all possible permutations of the given array. It starts by fixing one element (array[i]) at position i and then recursively explores permutations for the remaining elements (array[i+1:]).
The recursion continues until i reaches the last index (len(array) - 1).
For each position i, there are O(n−i) choices for the elements to swap with (j), where n is the length of the array.
Therefore, the total number of recursive calls made by permutations_helper() is the sum of O(n−i) for i ranging from 0 to n−1, which results in O(n!) recursive calls.
For each recursive call, this loop iterates over a decreasing number of elements, ranging from n−i to 1, where n is the length of the array and i is the current index.
Therefore, the total number of operations performed across all recursive calls is the sum of the product of the number of elements to iterate over and the number of recursive calls.
This results in a time complexity of O(n×n!).
The swap() function swaps two elements in constant time, so its contribution to the overall time complexity is negligible.
Space Complexity
Recursive Call Stack
The space complexity of the recursive call stack depends on the maximum depth of recursion, which is equal to the length of the input array n resulting in O(n).
Permutations List
The space required to store all permutations is O(n×n!), considering that there are n! permutations of an array of length n and each permutation has n elements.
Solution 3: Using itertools.permutations()
The itertools module in Python provides a function called permutations() that generates all possible permutations of a given iterable. It returns an iterator containing tuples of permutations. This function allows you to specify the length of permutations if needed.
from itertools import permutations
my_list = [1, 2, 3]
perm = permutations(my_list)
for p in perm:
print(p)
Solution 4: Using backtracking
Through backtracking algorithms, you build the permutations incrementally and backtrack when necessary to explore different possibilities.
Here's a general outline of how a backtracking algorithm for permutations works:
Initialization: Start with an empty permutation and a list of unused elements.
Base case: If all elements have been used, add the current permutation to the list of permutations and backtrack.
Backtracking: For each unused element, add it to the current permutation, mark it as used, recursively generate permutations with the updated permutation and list of unused elements, and then backtrack by removing the element from the permutation and marking it as unused.
Let's now implement a backtracking algorithm for generating permutations:
def backtrack_permutations(nums):
def backtrack(permutation):
# Base case: If the current permutation is of length equal to the input array
if len(permutation) == len(nums):
permutations.append(permutation[:]) # Append a copy of the current permutation
return
# Explore all possible choices for the next element in the permutation
for num in nums:
if num not in permutation:
permutation.append(num) # Add the element to the current permutation
backtrack(permutation) # Recursively generate permutations
permutation.pop() # Backtrack: Remove the last element from the current permutation
permutations = []
backtrack([])
return permutations
# Example usage:
nums = [1, 2, 3]
print(backtrack_permutations(nums))
This implementation uses a nested function backtrack() to generate permutations recursively.
The outer function backtrack_permutations() initializes the process and returns the list of permutations. During the exploration, each permutation is stored in the permutations list.
The algorithm ensures that no element is used more than once in any permutation by keeping track of used elements.
In all cases, the goal is to generate all possible arrangements of elements in the input sequence, considering the order of elements.
Time Complexity
Exploration of Permutations
For each recursive call to the backtrack() function, we explore all possible choices for the next element in the permutation. In the worst-case scenario, this involves exploring all elements of the input array for each position in the permutation. Therefore, the time complexity for exploring permutations is O(n!), where n is the number of elements in the input array.
Copying Permutations
In each recursive call, we make a copy of the current permutation before appending it to the list of permutations. Making a copy of a permutation takes O(n) time, where n is the length of the permutation.
Total Time Complexity
The overall time complexity of the backtracking solution is O(n×n!).
Space Complexity
Recursive Call Stack
The space complexity of the recursive call stack depends on the maximum depth of recursion, which is equal to the length of the input array n. Therefore, the space complexity due to the call stack is O(n).
Permutations List
The space required to store all permutations depends on the number of permutations generated. Since there are n! permutations of an array of length n, the space complexity for storing permutations is O(n!×n) (considering the average length of each permutation).
Temporary Storage
During the recursion, some additional space is required to maintain the current permutation. This temporary space is also O(n) since the length of the permutation is at most n.
Total Space Complexity
The overall space complexity of the backtracking solution is O(n+n!×n), which can be simplified to O(n!×n) as n! dominates when n is large.