Array permutations
Given an array, print all its permutations
Example
[1,2,3] => [1,2,3], [1,3,2], [2,1,3], [2,3,1], ...
Solution
- Use a recursive solution, swapping 2 array elements at a time in order
- Be sure to swap back the elements so that we can continue backtracking and do not repeat permutations
- Use this tree come up with the recursive solution
Code
def permute(arr, k)
i = k
while i <= k
swap(arr, i, k)
permute(arr, k+1)
swap(arr, i, k)
i += 1
end
if(k == arr.size - 1)
puts arr.inspect
end
end
def array_permutations(arr)
permute(arr, 0)
end
Alternate solution
- Use the next_permutation method
- Sort the given array in ascending order, then apply next permutation until all permutations have been generated
- 1,2,3 => 1,3,2 => 2,1,3 => 2,3,1 => ..
Complexity
Time: O(n * n!), due to n! permutations.