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

On 11/08/05, walter a kehowski <wkehowski@cox.net> wrote:
> Hello,
> 
> Since the original thread got a little long, I decided to post my next to
> last version in a new thread. My previous version gave results like
> [[1,4],7] for more than two arrays when you really wanted [1,4,7]. The trick
> is to flatten each element of the product. The following works for any
> number of arrays. Of course you might want a product in which the elements
> of that product are arrays. Any suggestions?
> 
> class Array
> 
>   def cartprod(b=[])
>     if b.empty? then
>       #assume self an array of arrays
>       inject {|cp,x| cp.cartprod(x) }
>     else
>       z = inject([]) {|a,x| b.inject(a) {|a,y| a << [x,y]}}
>       z.collect! {|x| x.flatten }
>     end
>   end
> 
> end
> 
> 
> a=[1,2,3]
> b=[4,5,6]
> c=[7,8,9]
> 
> # works fine
> p [a,b,c].cartprod
> 
> # doesn't work since [1,4,7,[10,11]] is [1,4,7,10,11]
> d=[10, [11,12]]
> p [a,b,c,d].cartprod
> 
> 
> 
> 

Here is my stab at the problem (I made it as a standalone method, as I
don't think of this operation as something that an array can do:

require 'test/unit'

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

class CarprodTest < Test::Unit::TestCase
  def test_simple
    assert_equal([[1, 'a'], [1, 'b'], 
		  [2, 'a'], [2, 'b'], 
		  [3, 'a'], [3, 'b']], 
		 cartprod([1,2,3], %w(a b)), 
                 'Simple Cartesian Product failed')
    assert_equal([[1, "a"], [1, "b"], [1, "c"], 
                  [2, "a"], [2, "b"], [2, "c"], 
		  [3, "a"], [3, "b"], [3, "c"]],
		 cartprod(1..3, 'a'..'c'),
                 'Simple Cartesian Product with ranges failed')
  end
  
  def test_multiple
    assert_equal([[1, 'a', :A], [1, 'a', :B], [1, 'b', :A], [1, 'b', :B], 
		  [2, 'a', :A], [2, 'a', :B], [2, 'b', :A], [2, 'b', :B]], 
		 cartprod([1,2], %w(a b), [:A, :B]), 
                 'Multiple Cartesian Product failed')
  end

  def test_array
    assert_equal([[1, ["a", "a"]], [1, ["b", "b"]], 
                  [2, ["a", "a"]], [2, ["b", "b"]], 
		  [3, ["a", "a"]], [3, ["b", "b"]]],
                 cartprod(1..3, [%w(a a), %w(b b)]),
		 'Cartesian Product with arrays failed')
  end

  def test_base_cases
    assert_equal([], cartprod([]), "Base case empty array is not correct")
    assert_equal([[1], [2], [3]], cartprod(1..3), "Base case single
array is not correct")
  end
end

regards,

Brian

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

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