Combinatorics for fun and profit

Posted by Giovanni Intini | Filed under Ruby

During my programming for fun moments I tend to always encounter a problem that needs to find combinations without repetitions for a set of data (numbers, objects, strings, letters, ...).

I have never been able to solve that problem in a way that satisfied me, and the languages I used didn’t have libraries for combinatorics that had a way to generate combinations without repetitions.

Yesterday a good friend of mine introduced me to the Set Puzzle, and, like I did for Word Challenge I had to try and attack the problem from a programming angle.

To do that I had to find once and for all a reusable way to generate combinations without repetitions. I did this time, and SetSolver was born.

You can check it out on GitHub, but I can’t help myself and not post the combinatorics code on this blog :) 

module ArrayExtensions
  def combinations_without_repetitions(k)
    combine(self, k)
  end
 
  private
  def combine(array, k)
    return [array] if k == array.size
    return array.collect {|e| [e]} if k == 1  
    results = []
    array[0..(array.size - k)].each_with_index do |val, idx|
      results += combine(array[(idx+1)..-1], k - 1).collect {|e| [val, e].flatten}
    end
    results
  end
end
 
Array.class_eval do
  include ArrayExtensions
end

Tags: ,
Permalink | Comments (0) | Nov 5, 2008

Comments are closed.