From: "Brian Schröder" <ruby.brian@...>
Date: 2005-08-12T18:33:11+09:00
Subject: Re: cartesian product - next to last version

On 12/08/05, Dave Burt <dave@burt.id.au> wrote:
> 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
> 
> 
> 
> 

Yielding the values is certainly a good idea, but it makes the code a
lot bigger. Anyhow, here is the recursive, yielding version.

def cartprod(base, *others)
  if block_given?
    if others.empty?
      base.each{|a| yield [a]}   
    else
      base.each do | a |
	cartprod(*others) do | b |
	  yield [a, *b] 
	end
      end
    end
    nil
  else
    return base.map{|a|[a]} if others.empty?
    others = cartprod(*others)
    base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, *b]) } }
  end
end


-- 
http://ruby.brian-schroeder.de/

Stringed instrument chords: http://chordlist.brian-schroeder.de/