10 September 2013

Algorithmathon

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

Less Is More ~ Older posts are available in the archive.