Prompt Detail:
Here's a recursive algorithm to find all permutations of an integer array in Python:
pythondef permutations(arr):
if len(arr) == 0:
return []
elif len(arr) == 1:
return [arr]
else:
result = []
for i in range(len(arr)):
elem = arr[i]
remaining = arr[:i] + arr[i+1:]
for p in permutations(remaining):
result.append([elem] + p)
return result
Here's how the function works:
- If the input array is empty, the function returns an empty array.
- If the input array has only one element, the function returns a single-element array containing that element.
- If the input array has more than one element, the function recursively finds all permutations of the remaining elements and appends the first element to each of those permutations.
For example, when the input is [1, 2, 3]
, the function first takes 1
and finds all permutations of [2, 3]
. Then, it takes 2
and finds all permutations of [1, 3]
. Finally, it takes 3
and finds all permutations of [1, 2]
. For each of these permutations, the function appends the first element to create a new permutation of the original input array.
The function returns a list of all permutations of the input array.