Velocity Reviews > Ruby > cartesian product - next to last version

# cartesian product - next to last version

walter a kehowski
Guest
Posts: n/a

 08-11-2005
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

Brian Schröder
Guest
Posts: n/a

 08-11-2005
On 11/08/05, walter a kehowski <(E-Mail Removed)> wrote:
> Hello,
>=20
> 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 tr=

ick
> 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 element=

s
> of that product are arrays. Any suggestions?
>=20
> class Array
>=20
> def cartprod(b=3D[])
> if b.empty? then
> #assume self an array of arrays
> inject {|cp,x| cp.cartprod(x) }
> else
> z =3D inject([]) {|a,x| b.inject(a) {|a,y| a << [x,y]}}
> z.collect! {|x| x.flatten }
> end
> end
>=20
> end
>=20
>=20
> a=3D[1,2,3]
> b=3D[4,5,6]
> c=3D[7,8,9]
>=20
> # works fine
> p [a,b,c].cartprod
>=20
> # doesn't work since [1,4,7,[10,11]] is [1,4,7,10,11]
> d=3D[10, [11,12]]
> p [a,b,c,d].cartprod
>=20
>=20
>=20
>=20

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 =3D 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'],=20
=09=09 [2, 'a'], [2, 'b'],=20
=09=09 [3, 'a'], [3, 'b']],=20
=09=09 cartprod([1,2,3], %w(a b)),=20
'Simple Cartesian Product failed')
assert_equal([[1, "a"], [1, "b"], [1, "c"],=20
[2, "a"], [2, "b"], [2, "c"],=20
=09=09 [3, "a"], [3, "b"], [3, "c"]],
=09=09 cartprod(1..3, 'a'..'c'),
'Simple Cartesian Product with ranges failed')
end
=20
def test_multiple
assert_equal([[1, 'a', :A], [1, 'a', :B], [1, 'b', :A], [1, 'b', :B],=
=20
=09=09 [2, 'a', :A], [2, 'a', :B], [2, 'b', :A], [2, 'b', :B]],=20
=09=09 cartprod([1,2], %w(a b), [:A, :B]),=20
'Multiple Cartesian Product failed')
end

def test_array
assert_equal([[1, ["a", "a"]], [1, ["b", "b"]],=20
[2, ["a", "a"]], [2, ["b", "b"]],=20
=09=09 [3, ["a", "a"]], [3, ["b", "b"]]],
cartprod(1..3, [%w(a a), %w(b b)]),
=09=09 '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

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

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

Gavin Kistner
Guest
Posts: n/a

 08-11-2005
--Apple-Mail-1--567785806
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed

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.
--Apple-Mail-1--567785806--

walter a kehowski
Guest
Posts: n/a

 08-11-2005
>
> 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

Dave Burt
Guest
Posts: n/a

 08-12-2005
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

Brian Schröder
Guest
Posts: n/a

 08-12-2005
On 12/08/05, Dave Burt <(E-Mail Removed)> wrote:
> Brian Schr=F6der offered:
> > def cartprod(base, *others)
> > return base.map{|a| [a] } if others.empty?
> > others =3D cartprod(*others)
> > base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
> > *b]) } }
> > end

>=20
> Wow - that's nice and functional!
>=20
> My procedural solution is much uglier, but it 1) isn't recursive and 2)
> yields results to a given block as it iterates.
>=20
> If given a block, the following will return nil, but pass the values into=

a
> given block:
>=20
> a=3D[[1,2,3],[4,5,6],[7,8,9]]
> a.cartprod do |a0e, a1e, a2e|
> # ...
> end
>=20
> class Array
> def cartprod
>=20
> unless block_given?
> ret =3D []
> cartprod {|tuple| ret << tuple}
> return ret
> end
> return if any? {|a| a.size =3D=3D 0 }
> index =3D [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] +=3D 1
> break
> else
> index[i] =3D 0
> end
> end
> end while index !=3D [0] * size
> end
> end
>=20
> Cheers,
> Dave
>=20
>=20
>=20
>=20

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]} =20
else
base.each do | a |
=09cartprod(*others) do | b |
=09 yield [a, *b]=20
=09end
end
end
nil
else
return base.map{|a|[a]} if others.empty?
others =3D cartprod(*others)
base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, *b]) }=
}
end
end

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

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

Brian Schröder
Guest
Posts: n/a

 08-12-2005
On 12/08/05, Brian Schr=F6der <(E-Mail Removed)> wrote:
> On 12/08/05, Dave Burt <(E-Mail Removed)> wrote:
> > Brian Schr=F6der offered:
> > > def cartprod(base, *others)
> > > return base.map{|a| [a] } if others.empty?
> > > others =3D 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 in=

to a
> > given block:
> >
> > a=3D[[1,2,3],[4,5,6],[7,8,9]]
> > a.cartprod do |a0e, a1e, a2e|
> > # ...
> > end
> >
> > class Array
> > def cartprod
> >
> > unless block_given?
> > ret =3D []
> > cartprod {|tuple| ret << tuple}
> > return ret
> > end
> > return if any? {|a| a.size =3D=3D 0 }
> > index =3D [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] +=3D 1
> > break
> > else
> > index[i] =3D 0
> > end
> > end
> > end while index !=3D [0] * size
> > end
> > end
> >
> > Cheers,
> > Dave
> >
> >
> >
> >

>=20
> Yielding the values is certainly a good idea, but it makes the code a
> lot bigger. Anyhow, here is the recursive, yielding version.
>=20
> 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 =3D cartprod(*others)
> base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, *b])=

} }
> end
> end
>=20
>=20

I've got some interesting benchmark results to share:
Benchmark.bm(35) do | b |=20
[[2, 16], [6,7], [25,4], [800,2]].each do | size, depth |
args =3D Array.new(depth) { Array.new(size) {|i| i} } =20
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.84=
0845)
Recursive Array iterated (2**16) 0.890000 0.130000 1.020000 ( 1.28=
7632)
Recursive Yielding (2**16) 3.910000 0.760000 4.670000 ( 4.77=
937
Procedural Yielding (2**16) 4.850000 0.890000 5.740000 ( 5.84=
7342)

Recursive Array (6**7) 1.690000 0.310000 2.000000 ( 2.02=
7407)
Recursive Array iterated (6**7) 2.300000 0.430000 2.730000 ( 2.72=
1382)
Recursive Yielding (6**7) 5.830000 1.330000 7.160000 ( 7.16=
6822)
Procedural Yielding (6**7) 11.200000 1.970000 13.170000 ( 13.44=
0081)

Recursive Array (25**4) 1.750000 0.360000 2.110000 ( 2.11=
8353)
Recursive Array iterated (25**4) 1.990000 0.510000 2.500000 ( 2.50=
7274)
Recursive Yielding (25**4) 9.130000 1.050000 10.180000 ( 10.22=
0420)
Procedural Yielding (25**4) 12.020000 2.120000 14.140000 ( 15.58=
0462)

Recursive Array (800**2) 3.750000 0.630000 4.380000 ( 4.37=
5153)
Recursive Array iterated (800**2) 3.050000 0.790000 3.840000 ( 3.83=
9810)
Recursive Yielding (800**2) 5.380000 0.930000 6.310000 ( 6.30=
8811)
Procedural Yielding (800**2) 17.170000 2.480000 19.650000 ( 20.67=
6642)

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
--=20
http://ruby.brian-schroeder.de/

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

Dave Burt
Guest
Posts: n/a

 08-12-2005
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

Brian Schröder
Guest
Posts: n/a

 08-12-2005
On 12/08/05, Dave Burt <(E-Mail Removed)> wrote:
> Interesting benchmarks. Thanks for sharing these and your code, Brian.
>=20
> 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.
>=20
> Any tips on learning to write code like your 3-line functonal recursive
> cartprod?
>=20
> Cheers,
> Dave
>=20

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

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

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

walter a kehowski
Guest
Posts: n/a

 08-12-2005
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://ruby.brian-schroeder.de/

## Question: Why the nil?