Cartesian product of arrays

Ruby
21

Hello,

“Trans” [email protected] wrote/schrieb
[email protected]:

On Jan 29, 3:53 pm, Thomas H. [email protected] wrote:

“Trans” [email protected] wrote/schrieb [email protected]:
It was just my first attempt to implement it, and that somehow
accidentally was the result. I’m not unlucky with it, at least it
seems to work with just a few lines of code.

understood. actually i have a VERY fast implementation already that
was written by Michael Neuman. to be so fast it’s very ugly though :slight_smile:
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 :slight_smile:

Regards
Thomas

22

On Jan 31, 2:05 pm, Thomas H. [email protected] wrote:

understood. actually i have a VERY fast implementation already that
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 :slight_smile:

Very good!!! I will do so then.

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

23

On Jan 31, 2:05 pm, Thomas H. [email protected] wrote:

understood. actually i have a VERY fast implementation already that
was written by Michael Neuman. to be so fast it’s very ugly though :slight_smile:
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.

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 :slight_smile:

Indeed! :slight_smile:

Thanks again,
T.

24

On Jan 31, 6:25 am, “Trans” [email protected] wrote:

– Maurice

Here ya go…

Err… fix the alias bug though (damn no-comma gets me every time!),
and the last def should be using the full name, ie. “def
cartesian_product”.

T.

25

“William J.” [email protected] wrote/schrieb
[email protected]:

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

26

On Jan 26, 4:52 am, Thomas H. [email protected] wrote:

t.each do |a|

=> [[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.

27

On Feb 2, 4:04 pm, Thomas H. [email protected] wrote:

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

28

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

29

Nanyang Z. wrote:

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/

30

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

31

Nanyang Z. wrote:

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/