### Algorithmathon Day 19: Combinations

*10 September 2013*

The challenge for us today is to find all the possible combinations of a set of numbers. When determining combinations the order is not important. This means that 123 is the equivalent of 321. The solution of this problem reminds me of the old adage about taking one step back for every two steps forward. Which in effect is what we do to determine the possible combinations. The solution is very similar to the Permutations of a String solution. The difference being that we start in position that is equal to the combination length desired. We work our way backwards from this position to the beginning of the array/string. Every step we make backwards we find the permutations from that location forwards. When it is all done you have your combinations.

We first prepare our RSpec tests. algorithm_array_spec.rb

`require 'spec_helper' describe AlgorithmArray do describe "Class" do it "should have method 'combinations'" do AlgorithmArray.method_defined?(:combinations).should be_true end end describe "Instance" do before(:each) do end it "should return 3 when '[].combinations(2).length' is called" do @array = AlgorithmArray.[](1,2,3) @array.combinations(2).length.should == 3 end it "should return 10 when '[].combinations(3).length' is called" do @array = AlgorithmArray.[](1,2,3,4,5) @array.combinations(3).length.should == 10 end it "should return 20 when '[].combinations(3).length' is called" do @array = AlgorithmArray.[](1,2,3,4,5,6) @array.combinations(3).length.should == 20 end it "should return 15 when '[1,2,3,4,5,6].combinations(4).length' is called" do @array = AlgorithmArray.[](1,2,3,4,5,6) @array.combinations(4).length.should == 15 end end end`

Finally the code to satisfy our tests. algorithm_array.rb

`class AlgorithmArray < Array attr_reader :iteration_count # # Finds the possible combinations of elements in the array. # * *Args* # - +combination_length+ -> The length of the combinations to be found. # * *Returns* # - An array containing all the possible combinations. def combinations(combination_length) @iteration_count=0 @level=0 unless combination_length.nil? || combination_length < 1 positions = combination_length - 1 return_array = Array.new() build_array = self[0..positions] return_array[return_array.length]= build_array.join() build_array.pop() positions.downto(0) do | position | combinate_by_recursion(return_array,build_array,positions,position,position+1) @level = @level - 1 build_array.pop() end return_array end end # # Using recursion finds the remaining possible combinations of elements in the array. The first # combination is found in the combinations method. The combinations method calls this method. # * *Args* # - +return_array+ -> An array referenced to act as a container for the combinations. # - +build_array+ -> An array acting as a stack to hold the combination currently under construction. # - +positions+ -> An integer that indicates the length of the combination # - +current_position+ -> The current position in the array being changed. # - +end_position+ -> The position in the array whose value is being pushed into the current position. # * *Returns* # - An array containing all the possible combinations. def combinate_by_recursion(return_array,build_array,positions,current_position,end_position) @level = @level + 1 if positions < current_position return_array[return_array.length]= build_array.join() return end while end_position < self.length @iteration_count = @iteration_count + 1 build_array.push(self[end_position]) combinate_by_recursion(return_array,build_array,positions,current_position + 1,end_position + 1) @level = @level - 1 build_array.pop() end_position=end_position+1 end end end`