Skip to content

Instantly share code, notes, and snippets.

@citrus
Created February 27, 2012 18:31
Show Gist options
  • Save citrus/1926032 to your computer and use it in GitHub Desktop.
Save citrus/1926032 to your computer and use it in GitHub Desktop.
A CartesianArray class in ruby
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 = [[]]
args = self + args
while [] != args
t, result = result, []
b, *args = args
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment