class Permute
  def initialize(array)
    @array = array
    @permutations = []
  end

  def permute
    _permute(0, @array.length)
    @permutations
  end

  private

  def _permute(left, right)
    if left == right
      @permutations << Array.new(@array)
      return
    end

    (left...right).each do |index|
      swap(left, index)
      _permute(left + 1, right)
      swap(index, left)
    end
  end

  def swap(l, r)
    return if l == r
    temp = @array[l]
    @array[l] = @array[r]
    @array[r] = temp
  end
end

def permute(array)
  Permute.new(array).permute
end