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.