cartesian product - next to last version

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://www.**--****.com/ 

Stringed instrument chords:  http://www.**--****.com/ 

In such cases, I use the Vector class (require 'matrix') as the  
'atomic' unit. Then Array#flatten doesn't peek inside the Vectors and  
flatten them inappropriately.

>

require 'matrix'
# see page 694 of PR
#

class Array

  def cartprod(b=[])

    if b.empty? then
      #assume self an array of arrays
      z=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

#Everything works
a=[1,2]
b=[4,5]
c=[7,8]
p [a,b,c].cartprod

d=[10, Vector[11,12]]
p [a,b,c,d].cartprod

Brian Schrer offered:

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://www.**--****.com/ 

Stringed instrument chords:  http://www.**--****.com/ 

Interesting benchmarks. Thanks for sharing these and your code, Brian.

I was initially surprised that your recursive code was quicker than my 
procedural, but when you look at them, it's obvious that my code is just 
doing more, unnecessarily, while yours is nice and simple.

Any tips on learning to write code like your 3-line functonal recursive 
cartprod?

Cheers,
Dave 

Thanks Dave,

regarding the tips you requested. The only thing that helps is to
think about how to split the problem recursively. It is like an
inductive proof. So it helps to make lots of inductive proofs
throughout your studies and get into a mindset for this. Then the
solution comes naturally. All a matter of experience I suppose (Though
I don't have that much, there are lots of more experienced people
here.)
Sorry if that is not of much help, maybe thinking about the proposed
solutions in this thread and the other threads will be more of a help.

best regards,

Brian

-- 
 http://www.**--****.com/ 

Stringed instrument chords:  http://www.**--****.com/ 

Hello,

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 # <--Why?
  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://www.**--****.com/ 

## Question: Why the nil?

Thanks, Brian. 

because otherwise the function would return the base array when
invoked with a block. And that would not make any sense for method
chaining. Nil will invoke an exception if a chained method is called
upon it.

regards,

Brian



-- 
 http://www.**--****.com/ 

Stringed instrument chords:  http://www.**--****.com/