combinations.rb

# possible solution for http://www.ruby-forum.com/topic/145570#887369 by Sergio Bayona
 
require 'test/unit'
 
# precondition: to_combine is expected to be in the format given below
# to_combine = [ set1 , set2 , ... , setn ]
# set = { key => values }
# key = any object with hash and eql? methods
# values = [ obj1 , obj2 , ... , objn ]
# obj = any ruby object
#
# invariant: the state of to_combine will not be altered
def combine( to_combine )
  # tests to ensure submitted data matches precondition
  raise "to_combine must be an array" unless to_combine.is_a? Array
  to_combine.each do |element|
    raise "sets should be hashes, which #{element.inspect} is not" unless element.is_a? Hash
    raise "sets should have one key value pair which #{element.inspect} does not" unless 1 == element.size
  end
  to_combine.each do |hash|
    raise "values should be arrays, which #{hash.values.first.inspect} is not" unless hash.values.first.is_a? Array
  end
  
  # if any values are empty, there is no combination which includes this set
  empty = [[]]
  return Array.new if to_combine.any? { |hash| hash.values == empty }
  
  _combine to_combine.map { |hash| hash.dup } # to prevent destructive calculations
end
 
# to be called by combine, in order to prevent expensive revalidating
def _combine( to_combine )
  return Array.new if to_combine.empty?                       # empty array means end recursion and rebuild
  current_key , current_values = Array(to_combine.pop).first  # extract current key/values pair, convert to array, strip outter array
  combined_without_current = _combine(to_combine)             # recursively calculate combinations without current
  combined_with_current = Array.new                           # build up results to return in this array
 
  # if original_combined is empty, then this is first return from recursive step, and results need to be manually populated
  return current_values.map { |value| { current_key => value } } if combined_without_current.empty?
 
  # for each current value, it must be combined with each of previous results
  current_values.each do |current_value|
    combined_without_current.each do |set_without_current|
      combined_with_current << set_without_current.merge( { current_key => current_value } )
    end
  end
  combined_with_current
end
 
 
class CombinerTest < Test::Unit::TestCase
  def teardown
    unless @skip_teardown
      a = @expected
      b = combine(@initial)
      assert_equal Array.new , (a-b)+(b-a) # it will say expected is [] , not sure if there is a more elegant way to handle this
    end
  end
  def test_bad_to_combine
    assert_raises( RuntimeError ) { combine(nil) }
    @skip_teardown = true
  end
  def test_bad_set
    assert_raises( RuntimeError ) { combine(['a']) }
    @skip_teardown = true
  end
  def test_bad_values_1
    assert_raises( RuntimeError ) { combine([{'a' => 'b'}]) }
    @skip_teardown = true
  end
  def test_bad_values_2
    assert_raises( RuntimeError ) { combine( [{'a' => ['b'],'c' => ['d']}] ) }
    @skip_teardown = true
  end
  def test_none
    @initial = []
    @expected = []
  end
  def test_empty_set
    @initial = [{:a => []}]
    @expected = []
  end
  def test_empty_set_2
    @initial = [{:a => [1,2]} , {:b => [3,4]} , {:b => []} , {:c => [5,6]} , {:d => [7,8]}]
    @expected = []
  end
  def test_empty_set_4
    @initial = [{:a => []} , {:b => [1]}]
    @expected = []
  end
  def test_empty_set_5
    @initial = [{:b => [1]} , {:a => []}]
    @expected = []
  end
  def test_cardinality_of_one_one
    @initial = [{:a => [1]}]
    @expected = [{:a => 1}]
  end
  def test_test_cardinality_of_three_one
    @initial = [{:a => [1]} , {:b => [2]} , {:c => [3]}]
    @expected= [{:a => 1 , :b => 2 , :c => 3}]
  end
  def test_test_cardinality_of_three_one
    @initial = [{:a => [1]} , {:b => [2]} , {:c => [3]}]
    @expected= [{:a => 1 , :b => 2 , :c => 3}]
  end
  def test_cardinality_off_two_two
    @initial = [{"a" => [1, 2]}, {"b" => [3, 4]}]
    @expected = [{"a" => 1, "b" => 3}, {"a" => 1, "b" => 4}, {"a" => 2, "b" => 3}, {"a" => 2, "b" => 4}]
  end
  def test_cardinality_off_three_two
    @initial = [{:a => [1,2]} , {:b => [3,4]} , {:c => [5,6]}]
    @expected = [ {:a => 1, :b => 3, :c => 5},
                  {:a => 1, :b => 4, :c => 5},
                  {:a => 2, :b => 3, :c => 5},
                  {:a => 2, :b => 4, :c => 5},
                  {:a => 1, :b => 3, :c => 6},
                  {:a => 1, :b => 4, :c => 6},
                  {:a => 2, :b => 3, :c => 6},
                  {:a => 2, :b => 4, :c => 6}]
  end
  def test_works_with_weird_keys_and_values
    @initial = [ {true => ['a',2]} , {false => [/b/,1/0.0]} ]
    @expected = [ { true => 'a' , false => /b/ } ,
                  { true => 'a' , false => 1/0.0 } ,
                  { true => 2 , false => /b/ } ,
                  { true => 2 , false => 1/0.0 } ]
  end
  def test_repeated_values_should_not_propogate
    @initial = [ {:a => [1,1]} , {:b => [2]} ]
    @expected = [ {:a => 1, :b => 2 } ]
  end
  def test_non_destructive
    @initial = [ {:a => [1,1]} , {:b => [2]} ]
    @expected = [ {:a => [1,1]} , {:b => [2]} ]
    combine(@initial)
    assert_equal @expected , @initial
    @skip_teardown = true
  end
end