String permutations

gistfile1.rb

# Returns all permutations of string s
def permutations(s)
  # For single characters just return one solution, the character
  if s.size <= 1
    [s] 
  else
    # calculate all permutations without the first character
    # and then iterate over each
    permutations(s[1..-1]).flat_map do |x|
      # for each position in permutation x
      0.upto(x.size).map do |i| 
        # insert the first character into permutation x 
        x.dup.insert(i, s[0])
      end
    end
  end
end