Sunday, November 25, 2007

Permutations in Ruby

During the long weekend I decided to break it down geek style with some Ruby, because that's the way I roll. Or anyway, I'm starting to learn a little Ruby and here's a first little exercise. I'm not sure if it's officially sanctioned Ruby idiom, but it's a start.

# find and print all permutations of a list

# find permutations recursively based on the idea that
# for each item in the list, there is a set of permutations
# that start with that item followed by some permutation of
# the remaining items.
def permute(list)
 if (list.length <= 1)
   return [list]
 end
 permutations = []
 list.each do |item|
   sublist_permutations = permute(list - [item])
   sublist_permutations.each do |permutation|
     permutation.unshift(item)
     permutations << permutation
   end
 end
 return permutations
end

# test our permute function
list = %w{ a b c d }
p = permute(list)
p.each do |permutation|
 puts "#{permutation.join(", ")}"
end