cartesian product - next to last version

W

walter a kehowski

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
 
B

Brian Schröder

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
Click to expand...

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

Gavin Kistner

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

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

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

walter a kehowski

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.
Click to expand...

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
 
D

Dave Burt

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
Click to expand...

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 < self.size - 1
index += 1
break
else
index = 0
end
end
end while index != [0] * size
end
end

Cheers,
Dave
 
B

Brian Schröder

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
Click to expand...
=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 < self.size - 1
index +=3D 1
break
else
index =3D 0
end
end
end while index !=3D [0] * size
end
end
=20
Cheers,
Dave
=20
=20
=20
=20
Click to expand...


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

Brian Schröder

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
Click to expand...

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 < self.size - 1
index +=3D 1
break
else
index =3D 0
end
end
end while index !=3D [0] * size
end
end

Cheers,
Dave
Click to expand...

=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
Click to expand...


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=
9378)
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/
 
D

Dave Burt

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
 
B

Brian Schröder

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
Click to expand...

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

walter a kehowski

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
 
B

Brian Schröder

Hello,
=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 # <--Why?
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
## Question: Why the nil?
=20
Click to expand...

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



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

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

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Fastest way to compute dot product (inner product) in Ruby? 4
Programming challenge: wildcard exclusion in cartesian products 78
Trouble with prediction code, for the life of me I can't figure out why it isnt running properly. Help would be appreciated. 0
Outputting signal values to terminal Within Character Array 0
Symbolic computation : the derivative of a product. 3
Finished a "teach yourself" book, what next? 33
use template or non template version? 1
[ANN] Natrix - The Named Matrix 1

Members online

Total: 42 (members: 2, guests: 40)
Robots: 639

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,057
Latest member
KetoBeezACVGummies

Latest Threads

Top