# cartesian product

Discussion in 'Ruby' started by walter a kehowski, Aug 7, 2005.

1. ### walter a kehowskiGuest

Hello,

How would I create a function that will take list (array) of integers and
return their cartesian product?

Thank You,

Walter Kehowski
nuby

walter a kehowski, Aug 7, 2005

2. ### Giovanni IntiniGuest

> How would I create a function that will take list (array) of integers and
> return their cartesian product?

You could do something like:

a =3D [1, 2, 3]

b =3D []

a.each do |elementone|
a.each do |elementtwo|
b << [elementone, elementtwo]
end
end

That should do the trick (I haven't tested it though)

Giovanni Intini, Aug 7, 2005

3. ### walter a kehowskiGuest

"Giovanni Intini" <> wrote in message
news:...
> How would I create a function that will take list (array) of integers and
> return their cartesian product?

>You could do something like:
>
>a = [1, 2, 3]
>
>b = []
>
>a.each do |elementone|
> a.each do |elementtwo|
> b << [elementone, elementtwo]
> end
>end
>
>That should do the trick (I haven't tested it though)

Giovanni,

Yes, that works. Another nuby question: How to make it a function? Such as
cartprod(a,b) returning c?

Walter

walter a kehowski, Aug 7, 2005
4. ### walter a kehowskiGuest

"Giovanni Intini" <> wrote in message
news:...
Remember that in Ruby you seldom have standalone functions. You should
probably create a class that has the cartprod method.

Giovanni,

Here's what I have so far:

def cartprod(a,b)

c=[]

a.each do |ae|
b.each do |be|
c << [ae, be]
end
end

return c

end

a=[1,2,3]

b=[4,5,6]

c=cartprod(a,b)

c.each { |ce| print ce,"\n" }

and this does print all the elements of c. Great. Now how do I do a class?
Can I create a new method for Array?

Walter Kehowski

walter a kehowski, Aug 7, 2005
5. ### Giovanni IntiniGuest

Remember that in Ruby you seldom have standalone functions. You should
probably create a class that has the cartprod method.

Giovanni Intini, Aug 7, 2005
6. ### dazGuest

walter a kehowski wrote:
>
>
> Here's what I have so far:
>
Code (Text):

>
> and this does print all the elements of c.
> Great. Now how do I do a class?
> Can I create a new method for Array?
>[/color]

class Array
def cartprod(b)
c=[]
each do |ae|
b.each do |be|
c << [ae, be]
end
end
c
end
end

a=[1,2,3]
b=[4,5,6]

c = a.cartprod(b)

c.each { |ce| p ce }

daz

daz, Aug 7, 2005
7. ### Giovanni IntiniGuest

if you want to create a new method for array just do

class Array
def cartprod(ary)
result =3D []
self.each do |ae|
ary.each do |be|
result << [ae, be]
end
end
result
end
end

this way you can have an array and do new_array =3D
source_array.cartprod(other_array)

Giovanni Intini, Aug 7, 2005
8. ### Robert KlemmeGuest

walter a kehowski <> wrote:
> "Giovanni Intini" <> wrote in message
> news:...
> Remember that in Ruby you seldom have standalone functions. You should
> probably create a class that has the cartprod method.
>
> Giovanni,
>
> Here's what I have so far:
>
> def cartprod(a,b)
>
> c=[]
>
> a.each do |ae|
> b.each do |be|
> c << [ae, be]
> end
> end
>
> return c
>
> end
>
> a=[1,2,3]
>
> b=[4,5,6]
>
> c=cartprod(a,b)
>
> c.each { |ce| print ce,"\n" }
>
> and this does print all the elements of c. Great. Now how do I do a
> class? Can I create a new method for Array?
>
> Walter Kehowski

Note that it might be more memory efficient to write a iteration method:

def cartprod(a,b)
a.each {|ae| b.each {|be| yield ae, be}}
end

Then you can also do this if needed

c=[]
cartprod(a,b) {|x,y| c << [x,y]}

If you just need every combination once the iteration approach is more
efficient.

Kind regards

robert

Robert Klemme, Aug 7, 2005
9. ### Martin DeMelloGuest

Robert Klemme <> wrote:
>
> Note that it might be more memory efficient to write a iteration method:
>
> def cartprod(a,b)
> a.each {|ae| b.each {|be| yield ae, be}}
> end
>
> Then you can also do this if needed
>
> c=[]
> cartprod(a,b) {|x,y| c << [x,y]}
>
> If you just need every combination once the iteration approach is more
> efficient.

Or even better,

if block_given?
yield ae, be
else
(c ||= []) << ae, be
end

martin

Martin DeMello, Aug 7, 2005
10. ### Randy KramerGuest

On Sunday 07 August 2005 10:51 am, Martin DeMello wrote:
> if block_given?
> yield ae, be
> else
> (c ||= []) << ae, be
> end

I'm sure you know what you're talking about, but I wonder how many others
will, even with comments. (Maybe I just need to go back to Pascal?)

Randy Kramer

Randy Kramer, Aug 7, 2005
11. ### Hal FultonGuest

Randy Kramer wrote:
> On Sunday 07 August 2005 10:51 am, Martin DeMello wrote:
>
>>if block_given?
>> yield ae, be
>>else
>> (c ||= []) << ae, be
>>end

>
>
> I'm sure you know what you're talking about, but I wonder how many others
> will, even with comments. (Maybe I just need to go back to Pascal?)

Haha... if it's this line you have trouble with

(c ||= []) << ae, be

it's not that hard.

The ||= is a well-known idiom -- same as c = c || [] here. Basically
"assign c this value, unless it is already non-nil."

So then you have either an existing array or an empty one.
Then you can append (<<) onto it.

If it's the yield that bothers you, just study a bit more
Ruby. Pascal was wonderful in 1980 -- unless you already knew
something better -- but I'm content to let it go now.

Hal

Hal Fulton, Aug 7, 2005
12. ### Randy KramerGuest

On Sunday 07 August 2005 01:22 pm, Hal Fulton wrote:
> Haha... if it's this line you have trouble with
>
> (c ||= []) << ae, be
>
> it's not that hard.
>
> The ||= is a well-known idiom -- same as c = c || [] here. Basically
> "assign c this value, unless it is already non-nil."
>
> So then you have either an existing array or an empty one.
> Then you can append (<<) onto it.

Hal,

Thanks--that line was the most confusing. (Yield I at least have a clue about,
though I would need to think about it in this context a little more.)

regards,

Randy Kramer

>
> If it's the yield that bothers you, just study a bit more
> Ruby. Pascal was wonderful in 1980 -- unless you already knew
> something better -- but I'm content to let it go now.
>
>
> Hal

Randy Kramer, Aug 7, 2005
13. ### walter a kehowskiGuest

Hello,

Here's what I have so far, combining the previous suggestions of Robert
Klemme and Martin DeMello:

class Array

def cartprod(a,b)
a.each {|ae|
b.each {|be|
if block_given?
yield ae,be
else
(c ||= []) << ae,be
end
end

end #Array

However,

c=cartprod([1,2,3],[4,5,6])

c.each { |ce| print ce,"\n" }

gives the following syntax error:

cartprod.rb:24: syntax error
(c ||= []) << ae,be
^
cartprod.rb:26: syntax error
cartprod.rb:132: syntax error

and I would like to take the cartesian product of an arbitrary number of
sets in the most elegant way.

walter a kehowski, Aug 7, 2005
14. ### walter a kehowskiGuest

Hello,

The following is not in the spirit of previous comments

class Array

def cartprod(b)

c=[]
each {|ae| b.each {|be| c << [ae, be] } }
c.collect! {|ce| ce.flatten}

end #cartprod

end #Array

a=[[1,2,3],[4,5,6],[7,8,9]]

c=a[0]
as=a.slice(1..a.length-1)
as.each {|ase| c=c.cartprod(ase) }
c.each {|ce| ce.each {|x| print x," " }; print "\n" }

Would the following be desirable? If cartprod has two or more arguments, do
the usual thing, but if it has just one, it takes the cartesian product with
that argument, i.e, cartprod(a) gives cartprod(a,a) or a.cartprod(a), etc.

And thanks for all the suggestion so far. I usually just play around with
Perl but got \$#@% fatigue. It was a toss-up between Python and Ruby so here
I am.

Walter Kehowski

walter a kehowski, Aug 7, 2005
15. ### Dave BurtGuest

walter a kehowski wrote...
> cartprod.rb:24: syntax error
> (c ||= []) << ae,be
> ^
> cartprod.rb:26: syntax error
> cartprod.rb:132: syntax error

class Array
def cartprod(b)
each do |ae|
b.each do |be|
if block_given?
yield ae, be # <-- you can yield multiple objects
else
(c ||= []) << [ae, be] # <-- you need to put (ae, be) in a
single
# object (i.e. an array) to put in an
array
end
end # <-- you had missed 2 closing braces (line 132 error)
end
c # <-- you want to return this if no block was given
end
end

Cheers,
Dave

Dave Burt, Aug 7, 2005
16. ### Dave BurtGuest

walter a kehowski...
> c=[]
> each {|ae| b.each {|be| c << [ae, be] } }
> c.collect! {|ce| ce.flatten}

Flatten is going to squash nested arrays. Maybe:

inject([]) {|c, ae| c.concat b.map {|be| [ae, be] } }

>
> c=a[0]
> as=a.slice(1..a.length-1)

You can do this (in Perl, too):
as = a.slice(1..-1)
or this:
as = a[1..-1]

> as.each {|ase| c=c.cartprod(ase) }
> c.each {|ce| ce.each {|x| print x," " }; print "\n" }
>
> Would the following be desirable? If cartprod has two or more arguments,
> do the usual thing, but if it has just one, it takes the cartesian product
> with that argument, i.e, cartprod(a) gives cartprod(a,a) or a.cartprod(a),
> etc.

I wouldn't. Typing an extra argument makes the function clearer - cartesian
product is a two-array function.

> And thanks for all the suggestion so far. I usually just play around with
> Perl but got \$#@% fatigue. It was a toss-up between Python and Ruby so
> here I am.

You're welcome.

Cheers,
Dave

Dave Burt, Aug 7, 2005
17. ### walter a kehowskiGuest

Hello,

If one defines

class Array
def cartprod(b)
each do |ae|
b.each do |be|
if block_given?
yield ae, be
else
(c ||= []) << [ae, be]
end
end
end
c
end
end

then

a=[[1,2,3],[4,5,6],[7,8,9]]

c=cartpord(a.slice(0..-1))

c.each {|ce| ce.each {|x| print x," " }; print "\n" }

gives the error

cartprod.rb:45: undefined method `cartpord' for main:Object (NoMethodError)

and

a=[[1,2,3],[4,5,6],[7,8,9]]

c=a[0]

b=a.slice(1..-1)

b.each{|be| c=c.cartprod(be) }

c.each {|ce| ce.each {|x| print x," " }; print "\n" }

gives the error

cartprod.rb:24:in `cartprod': undefined local variable or method `c' for [1,
2, 3]:Array (NameError)
from cartprod.rb:49
from cartprod.rb:49:in `each'
from C:/Documents and Settings/walter/My Documents/cartprod.rb:49

and, finally,

a=[[1,2,3],[4,5,6],[7,8,9]]

c=cartprod(a)

c.each {|ce| ce.each {|x| print x," " }; print "\n" }

gives the error

cartprod.rb:45: undefined method `cartprod' for main:Object (NoMethodError)

Well, I'm clearly plying around trying to get it JUST RIGHT.

Walter Kehowski

walter a kehowski, Aug 8, 2005
18. ### Dave BurtGuest

Walter,

One error is mine, two are yours.

> c=cartpord(a.slice(0..-1))
> ...
> cartprod.rb:45: undefined method `cartpord' for main:Object
> (NoMethodError)

You've got a typo here (or -> ro). Also, cartprod is defined as a method of
Arrays, so you can't use it as a function like that.

> b.each{|be| c=c.cartprod(be) }
> ...
> cartprod.rb:24:in `cartprod': undefined local variable or method `c' for
> [1, 2, 3]:Array (NameError)
> from cartprod.rb:49
> from cartprod.rb:49:in `each'
> from C:/Documents and Settings/walter/My Documents/cartprod.rb:49

This is a bug in my untested code. It occurs because c is not defined
outside the inner block. This version will actually work (I've renamed c to
prod):

class Array
def cartprod(b)
prod = ([] unless block_given?)
each do |ae|
b.each do |be|
if block_given?
yield ae, be
else
prod << [ae, be]
end
end
end
prod
end
end

> c=cartprod(a)
> ...
> cartprod.rb:45: undefined method `cartprod' for main:Object
> (NoMethodError)

Again, cartprod has to be used on an array, like this:

a=[[1,2,3],[4,5,6],[7,8,9]]
b=a.shift
a.each do |ae|
b = b.cartprod(ae)
# the following line is so you don't get [[[1,4],7], [[1,4],8] ...
b.map! {|be| be.flatten } if b[0][0].is_a? Array
end
b #=> [[1, 4, 7], [1, 4, 8] ... [3, 6, 9]] #(27 elements)

But if you want to cartesianly-multiply multiple arrays, maybe you want
something more like this:

class Array
def cartprod
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

This will return nil, but pass the values you want into a given block:

a=[[1,2,3],[4,5,6],[7,8,9]]
a.cartprod do |a0e, a1e, a2e|
# ...
end

You should easily be able to change it to return an array if you need to.

Cheers,
Dave

Dave Burt, Aug 8, 2005

20. ### Martin DeMelloGuest

walter a kehowski <> wrote:
>
> cartprod.rb:24: syntax error
> (c ||= []) << ae,be
> ^
> cartprod.rb:26: syntax error
> cartprod.rb:132: syntax error

My mistake, sorry. Should be (c ||= []) << [ae, be]

> and I would like to take the cartesian product of an arbitrary number of
> sets in the most elegant way.

Define a cartprod2 that takes the cartesian product of two arrays.
Define base cases sensibly - cartprod2([], a) = a.map {|i| } and
cartprod2(a,b) = a.each {|i| b.each {|j| c << i.concat(j)}}

Use that as a helper function for cartprod thus:

def cartprod(*arrays)
arrays.inject([]) {|prod, ary| cartprod2(prod, ary)}
end

Untested, but that's the general idea.

martin

Martin DeMello, Aug 8, 2005