Algorithmathon Day 19: Combinations
Created: 10 September 2013 Modified:
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 th* 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

tags: