cartesian product of arrays

[Thomas Hafner]

Hello,

understood. actually i have a VERY fast implementation already that
was written by Michael Neuman. to be so fast it's very ugly though
want to see?

I was curious enough to run both - my code and the one that you've
adapted from code by Michael Neuman - in irb, and my impression is,
that my code is even much faster. So if you're interested in providing
a really good library, please feel free to benchmark and chose the
best one according to your benchmark results.

Sorry that I did no benchmark myself (I'm still Ruby newbie); I just
run (1..15).cartesian_product((1..15),(1..15)) with both variants.

In addition I don't find my implementation ugly, so there's a real
chance to get several advantages at the same time

Regards
Thomas

 

[Trans]

Hello,




I was curious enough to run both - my code and the one that you've
adapted from code by Michael Neuman - in irb, and my impression is,
that my code is even much faster. So if you're interested in providing
a really good library, please feel free to benchmark and chose the
best one according to your benchmark results.

Sorry that I did no benchmark myself (I'm still Ruby newbie); I just
run (1..15).cartesian_product((1..15),(1..15)) with both variants.

In addition I don't find my implementation ugly, so there's a real
chance to get several advantages at the same time

Very good!!! I will do so then.

Thanks, and I'll let you know how it turns out.
T.

 

[Trans]

Hello,




I was curious enough to run both - my code and the one that you've
adapted from code by Michael Neuman - in irb, and my impression is,
that my code is even much faster. So if you're interested in providing
a really good library, please feel free to benchmark and chose the
best one according to your benchmark results.

Very Good! And you are quite right. I must have gotten this confused
with some other function. I've put you code in, and credited you.
Thanks lots for this! There was only one downside in that using the
block form couldn't run on the each possibility as it is computed, but
that's okay. I just tied the block into the end result:

def cartesian_product(*enums, &block)
result = [[]]
while [] != enums
t, result = result, []
b, *enums = enums
t.each do |a|
b.each do |n|
result << a + [n]
end
end
end
if block_given?
result.each{ |e| block.call(e) }
else
result
end
end

Sorry that I did no benchmark myself (I'm still Ruby newbie); I just
run (1..15).cartesian_product((1..15),(1..15)) with both variants.

In addition I don't find my implementation ugly, so there's a real
chance to get several advantages at the same time

Indeed!

Thanks again,
T.

 

[William James]

Hello,

did I miss some standard library function? Anyway, then I'll do it on
my own:

def cartprod(*args)
result = [[]]
while [] != args
t, result = result, []
b, *args = args
t.each do |a|
b.each do |n|
result << a + [n]
end
end
end
result
end

Example:
cartprod([1,2],[3,4,5],[6,7,8])
=> [[1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 4, 6], [1, 4, 7], [1, 4, 8],
[1, 5, 6], [1, 5, 7], [1, 5, 8], [2, 3, 6], [2, 3, 7], [2, 3, 8],
[2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 5, 6], [2, 5, 7], [2, 5, 8]]

Regards
Thomas

Here's a shorter but slower way.

def cart_prod( *args )
args.inject([[]]){|old,lst|
lst.inject([]){|new,e|
new + old.map{|c| c.dup << e}}}
end

Its results are ordered differently.

 

[Thomas Hafner]

Here's a shorter but slower way.

def cart_prod( *args )
args.inject([[]]){|old,lst|
lst.inject([]){|new,e|
new + old.map{|c| c.dup << e}}}
end

Wow, it's really short. Maybe it's not slower at all. Did you just
that? Or did you compare it actually?

Regards
Thomas

 

[William James]

Here's a shorter but slower way.

def cart_prod( *args )
args.inject([[]]){|old,lst|
lst.inject([]){|new,e|
new + old.map{|c| c.dup << e}}}
end

Wow, it's really short. Maybe it's not slower at all. Did you just
that? Or did you compare it actually?

Regards
Thomas

I tested it; it's slower. This one isn't quite as slow.

def cart_prod( *args )
args.inject([[]]){|old,lst|
new = []
lst.each{|e| new += old.map{|c| c.dup << e }}
new
}
end

 

[Nanyang Zhan]

well, then can anyone tell me which one is the best?

 

[Adriano Mitre]

well, then can anyone tell me which one is the best?

Unfortunately, these methods uses too much memory, storing the whole
cartesian product Array in memory even its elements are needed only one
at a time. One nicer alternative is the Cartesian module:

"The Cartesian module provide methods for the calculation of the
cartesian producted between two enumberable objects. It can also be
easily mixed in into any enumberable class, i.e. any class with
Enumerable module mixed in."

The Cartesian module is available at
http://rubyforge.org/projects/cartesian/

 

[Adriano Mitre]

well, then can anyone tell me which one is the best?

Unfortunately, these methods use too much memory, storing the whole
cartesian product Array in memory even its elements are needed only one
at a time. A nicer alternative is the Cartesian module:

"The Cartesian module provide methods for the calculation of the
cartesian producted between two enumberable objects. It can also be
easily mixed in into any enumberable class, i.e. any class with
Enumerable module mixed in."

The Cartesian module is available at
http://rubyforge.org/projects/cartesian/

 

[Adriano Mitre]

Update: although gems releases are still being published at RubyForge as
well as RubyGems, the project is now hosted at GitHub and its new
homepage is http://adrianomitre.github.com/cartesian/website/index.html