cartesian_array.rb

require "minitest/autorun"

# Each member of a Cartesian Array corresponds to the selection of one element each in every one of those sets. 
# http://en.wikipedia.org/wiki/Cartesian_product

class CartesianArray < Array

  # CartesianArray.new([0,1], [a,b], etc)
  def initialize(*args)
    super args
  end
  
  # array = CartesianArray.new([0,1])
  # array.product(%w(a b))
  # => [[0, "a"], [0, "b"], [1, "a"], [1, "b"]]
  def product(*args)
    result = [[]]
    while [] != args #loop until we've popped all off stack
      t, result = result, []
      b, *args = args #pop the first array off the stack
      t.each do |a|
        b.each do |n|
          result << a + [n]
        end
      end
    end
    result
  end

end

describe 'CartesianArray' do

  it "calculates cartesian product" do
    CartesianArray.new([0,1], [0,1]).product.must_equal [[0, 0], [0, 1], [1, 0], [1, 1]]
  end
  
  it "calculates cartesian product with an argument" do
    CartesianArray.new([0,1]).product([0,1]).must_equal [[0, 0], [0, 1], [1, 0], [1, 1]]
  end
  
  it "calculates cartesian product with string values" do
    CartesianArray.new([0,1], %w(s m)).product.must_equal [[0, "s"], [0, "m"], [1, "s"], [1, "m"]]
  end
  
  it "calculates cartesian product with arrays with uneven numbers" do
    CartesianArray.new([0,1], %w(s m l)).product.must_equal [[0, "s"], [0, "m"], [0, "l"], [1, "s"], [1, "m"], [1, "l"]]
  end
  
  it "calculates cartesian product with more than two arrays" do
    CartesianArray.new([0,1], %w(s m l), %w(a b)).product.must_equal [
      [0, "s", "a"],
      [0, "s", "b"],
      [0, "m", "a"],
      [0, "m", "b"],
      [0, "l", "a"],
      [0, "l", "b"],
      [1, "s", "a"],
      [1, "s", "b"],
      [1, "m", "a"],
      [1, "m", "b"],
      [1, "l", "a"],
      [1, "l", "b"]
    ]
  end

  it "calculates cartesian product over and over again" do
    CartesianArray.new([0,1]).product(%w(s m)).product(%w(a b)).must_equal [
      [[0, "s"], "a"],
      [[0, "s"], "b"],
      [[0, "m"], "a"],
      [[0, "m"], "b"],
      [[1, "s"], "a"],
      [[1, "s"], "b"],
      [[1, "m"], "a"],
      [[1, "m"], "b"]
    ]
  end

end