From: Dave Burt <dave@...>
Date: 2005-08-12T16:56:11+09:00
Subject: Re: cartesian product - next to last version

Brian Schr�der offered:
> def cartprod(base, *others)
>   return base.map{|a| [a] } if others.empty?
>   others = cartprod(*others)
>   base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, 
> *b]) } }
> end

Wow - that's nice and functional!

My procedural solution is much uglier, but it 1) isn't recursive and 2) 
yields results to a given block as it iterates.

If given a block, the following will return nil, but pass the values into a 
given block:

a=[[1,2,3],[4,5,6],[7,8,9]]
a.cartprod do |a0e, a1e, a2e|
  # ...
end

class Array
  def cartprod

    unless block_given?
      ret = []
      cartprod {|tuple| ret << tuple}
      return ret
    end
    return if any? {|a| a.size == 0 }
    index = [0] * size
    begin
      yield *zip(index).map {|a| a[0][a[1]] }
      (index.size - 1).downto(0) do |i|
        if index[i] < self[i].size - 1
          index[i] += 1
          break
        else
          index[i] = 0
        end
      end
    end while index != [0] * size
  end
end

Cheers,
Dave