#Permutations Recursive

def _add_head(head, res)
  out = []
  res.each do |permutation|
    0.upto(permutation.length) do |i|
      _insert!(i, head, permutation, out)
    end
  end
  out
end

def _insert!(i, head, permutation, out)
  if i == 0
    out << [head, *permutation[0..-1]]
  elsif permutation[i] == nil
    out << [*permutation[0..-1], head]
  else
    out << [*permutation[0...i], head, *permutation[i..-1]]
  end
end

def permutations(res)
  return [res] if res.length == 1
  _add_head(res[0], permutations(res[1..-1]))
end

print permutations([1,2,3,4])