# 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

···

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

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

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.

···

On Aug 11, 2005, at 5:06 AM, walter a kehowski wrote:

Of course you might want a product in which the elements
of that product are arrays. Any suggestions?

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 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

···

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

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

I've got some interesting benchmark results to share:
Benchmark.bm(35) do | b |
[[2, 16], [6,7], [25,4], [800,2]].each do | size, depth |
args = Array.new(depth) { Array.new(size) {|i| i} }
b.report("Recursive Array (#{size}**#{depth})") do cartprod(*args) end
b.report("Recursive Array iterated (#{size}**#{depth})") do
cartprod(*args).each do | e | end end
b.report("Recursive Yielding (#{size}**#{depth})") do
cartprod_y(*args) do | e | end end
b.report("Procedural Yielding (#{size}**#{depth})") do
args.cartprod do | *e | end end
puts
end
end

user system total real
Recursive Array (2**16) 0.610000 0.130000 0.740000 ( 0.840845)
Recursive Array iterated (2**16) 0.890000 0.130000 1.020000 ( 1.287632)
Recursive Yielding (2**16) 3.910000 0.760000 4.670000 ( 4.779378)
Procedural Yielding (2**16) 4.850000 0.890000 5.740000 ( 5.847342)

Recursive Array (6**7) 1.690000 0.310000 2.000000 ( 2.027407)
Recursive Array iterated (6**7) 2.300000 0.430000 2.730000 ( 2.721382)
Recursive Yielding (6**7) 5.830000 1.330000 7.160000 ( 7.166822)
Procedural Yielding (6**7) 11.200000 1.970000 13.170000 ( 13.440081)

Recursive Array (25**4) 1.750000 0.360000 2.110000 ( 2.118353)
Recursive Array iterated (25**4) 1.990000 0.510000 2.500000 ( 2.507274)
Recursive Yielding (25**4) 9.130000 1.050000 10.180000 ( 10.220420)
Procedural Yielding (25**4) 12.020000 2.120000 14.140000 ( 15.580462)

Recursive Array (800**2) 3.750000 0.630000 4.380000 ( 4.375153)
Recursive Array iterated (800**2) 3.050000 0.790000 3.840000 ( 3.839810)
Recursive Yielding (800**2) 5.380000 0.930000 6.310000 ( 6.308811)
Procedural Yielding (800**2) 17.170000 2.480000 19.650000 ( 20.676642)

In these benchmarks the recursive version is a lot faster. Beware that
only creating and discarding the block is not a good measure,
therefore I also included an iteration about the returned array for
the array method. As you see it depends on the characteristics of the
argument which method is fastest.

regards,

Brian

···

On 12/08/05, Brian Schröder <ruby.brian@gmail.com> wrote:

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

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

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

···

## Question: Why the nil?

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

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

···

On 12/08/05, walter a kehowski <wkehowski@cox.net> wrote:

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

## Question: Why the nil?

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

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

···

On 12/08/05, Dave Burt <dave@burt.id.au> wrote:

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

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

Thanks, Brian.