# Cartesian product of arrays **URL:** \ **Category:** Ruby\ **Created:** [January 26, 2007, 12:05pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464 "2007-01-26T12:05:49Z")\ **Posts on this page:** 11\ **Page:** 2
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [January 31, 2007, 8:05pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/21 "2007-01-31T20:05:57Z")
Hello, “Trans” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > On Jan 29, 3:53 pm, Thomas H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > > “Trans” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > 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 🙂 > 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 ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [January 31, 2007, 8:50pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/22 "2007-01-31T20:50:01Z")
On Jan 31, 2:05 pm, Thomas H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 🙂 Very good!!! I will do so then. Thanks, and I’ll let you know how it turns out. T. ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [January 31, 2007, 9:33pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/23 "2007-01-31T21:33:04Z")
On Jan 31, 2:05 pm, Thomas H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 🙂 > > 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 🙂 Indeed! 🙂 Thanks again, T. ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [January 31, 2007, 4:04pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/24 "2007-01-31T16:04:29Z")
On Jan 31, 6:25 am, “Trans” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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. ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [February 2, 2007, 11:11pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/25 "2007-02-02T23:11:32Z")
“William J.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > 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 ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [February 1, 2007, 9:31pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/26 "2007-02-01T21:31:04Z")
On Jan 26, 4:52 am, Thomas H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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. ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [February 3, 2007, 2:35am UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/27 "2007-02-03T02:35:47Z")
On Feb 2, 4:04 pm, Thomas H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [January 10, 2008, 10:23am UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/28 "2008-01-10T10:23:23Z")
well, then can anyone tell me which one is the best? ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [July 26, 2009, 11:39pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/29 "2009-07-26T23:39:24Z")
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/](http://rubyforge.org/projects/cartesian/) ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [January 5, 2011, 9:58am UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/30 "2011-01-05T09:58:07Z")
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](http://adrianomitre.github.com/cartesian/website/index.html) ---
**Author:** ![samoht](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/ac8455/32.png) [@samoht](https://www.ruby-forum.com/u/samoht)\ **Post date:** [July 26, 2009, 11:40pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/31 "2009-07-26T23:40:45Z")
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/](http://rubyforge.org/projects/cartesian/) [Previous page](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464.md?page=1)