cartesian product

[walter a kehowski]

Hello,

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

Thank You,

Walter Kehowski
nuby

 

[Giovanni Intini]

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)

 

[walter a kehowski]

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]

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

 

[Giovanni Intini]

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

 

[daz]

Here's what I have so far:

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?
[/QUOTE]


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

 

[Giovanni Intini]

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)

 

[Robert Klemme]

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

 

[Martin DeMello]

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

 

[Randy Kramer]

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

 

[Hal Fulton]

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

 

[Randy Kramer]

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

 

[walter a kehowski]

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]

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

 

[Dave Burt]

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]

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

 

[walter a kehowski]

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

 

[Dave Burt]

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

 

[Gene Tani]

can we merge 2 threads

http://groups-beta.google.com/group...:comp.lang.ruby&rnum=6&hl=en#608d3656142aeba6

 

[Martin DeMello]

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