Cartesian Product Ruby

Question

class CartesianProduct
include Enumerable
# your code here
end
#Examples of use
c = CartesianProduct.new([:a,:b], [4,5])
c.each { |elt| puts elt.inspect }
# [:a, 4]
# [:a, 5]
# [:b, 4]
# [:b, 5]
c = CartesianProduct.new([:a,:b], [])
c.each { |elt| puts elt.inspect }
# (nothing printed since Cartesian product
# of anything with an empty collection is empty)

I am new to ruby. And I understand how to define a instance method of Cartesian Product, but I have no clue to this. How should I construct the class object to fulfill the requirement.

Answer 1

I suggest using Array#product.

[:a, :b].product [4,5]

Which will yield the output you want.

irb(main):001:0> [:a, :b].product [4,5]
=> [[:a, 4], [:a, 5], [:b, 4], [:b, 5]]
irb(main):002:0> 

If you want a lazy generator of permutations, I have written something like this before. But I warn you, if you have a large number of permutations to compute it might take a while. You should be able to take what you need from the first 40 - 45 lines of this file (this file was an experiment anyway).

The trick is to build enumerators using Ruby 1.9.2 to work your way through an array of arrays. So you first build an enumerator that will endlessly cycle through an array, and in your array-of-array enumerator you track the first output set and end the loop when that is hit a second time. This was the only way I could figure out how to terminate such a loop.

def infinite_iterator(array)
  Enumerator.new do |result|
    loop do
      array.cycle { |item| result << item }
    end
  end
end

def cartesian_iterator(data)
  Enumerator.new do |result|
    first = data.map { |p| p.next }
    result << first

    i = 1
    parts = first.dup
    loop do
      parts[2-i] = data[2-i].next
      break if parts == first

      result << parts.join
      i = ((i + 1) % parts.size)
    end
  end
end

array = [ infinite_iterator([:a,:b]), infinite_iterator([4,5]) ]
generator = cartesian_iterator(array)

generator.each { |a| p a }