# 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:** 20\ **Page:** 1
**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 26, 2007, 12:05pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/1 "2007-01-26T12:05:49Z")
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 ---
**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 26, 2007, 12:42pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/2 "2007-01-26T12:42:58Z")
Thomas H. wrote: > Hello, > > did I miss some standard library function? Anyway, then I’ll do it on > my own: > Cool! Just a suggestion: it is also possible to reopen Enumerable and put your code there - in this case, all enumerable types will have this functionality (e.g. Sets), not only Arrays. Also it is maybe more intuitive (for me at least) to write: first\_ary.cartprod second\_ary Best wishes, Peter \_\_ [http://www.rubyrailways.com](http://www.rubyrailways.com) ---
**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 26, 2007, 1:41pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/3 "2007-01-26T13:41:13Z")
Peter S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > Also it is maybe more intuitive (for me at least) to write: > > first\_ary.cartprod second\_ary How should my example then look like? It can’t be [1,2].cartprod([3,4,5]).cartprod([6,7,8]), because then the result would be different: [[[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]] Do you appreciate [1,2].cartprod([3,4,5], [6,7,8]) ? 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 26, 2007, 1:51pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/4 "2007-01-26T13:51:14Z")
Thomas H. wrote: > Peter S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > > Also it is maybe more intuitive (for me at least) to write: > > > > first\_ary.cartprod second\_ary > > How should my example then look like? > Well, you are right… it is much less intuitive if you have 3 or more > arrays. However, I think your example, i.e. [1,2].cartprod([3,4,5], [6,7,8]) is perfectly OK! Basically what changes is that you will refer to the array [1,2] as self (in Enumerable), and not as the first parameter (as in your original cartprod function). Bye, Peter \_\_ [http://www.rubyrailways.com](http://www.rubyrailways.com) ---
**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 27, 2007, 7:15pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/5 "2007-01-27T19:15:05Z")
Thomas H. wrote: > Peter S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > > Just a suggestion: it is also possible to reopen Enumerable and put your > > code there - in this case, all enumerable types will have this > > functionality (e.g. Sets), not only Arrays. > > Does that follow your suggestion?: > Exactly! Cheers, Peter \_\_ [http://www.rubyrailways.com](http://www.rubyrailways.com) ---
**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 27, 2007, 7:06pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/6 "2007-01-27T19:06:04Z")
Peter S. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > Just a suggestion: it is also possible to reopen Enumerable and put your > code there - in this case, all enumerable types will have this > functionality (e.g. Sets), not only Arrays. Does that follow your suggestion?: #\ module Enumerable def cartprod(\*args) result = [[]] ([self] + args).each do |b| t, result = result, [] t.each do |a| b.each do |n| result \<\< a + [n] end end end result end end #/// Example: (1…2).cartprod((3…5), (6…8)) 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 29, 2007, 8:04am UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/7 "2007-01-29T08:04:55Z")
On 1/26/07, Thomas H. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > did I miss some standard library function? Anyway, then I’ll do it on > my own: I wrote once like that. My product.rb is a mixin for enumerable. [http://www.notwork.org/~gotoken/ruby/p/product/ruby-product-1.0.0.tar.gz](http://www.notwork.org/~gotoken/ruby/p/product/ruby-product-1.0.0.tar.gz) hope this helps, gotoken ---
**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 29, 2007, 12:55pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/8 "2007-01-29T12:55:39Z")
“karoyakani” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote/schrieb [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > def cartprod(\*args) > args.shift.cartprod(args) > ^^^^ > args.shift.cartprod(_args) > with the additional ``_‘’ would be better … > end > > Then both forms work as below: > p (1…2).cartprod((3…5), (6…8)) > p cartprod([1,2],[3,4,5],[6,7,8]) … otherwise the second statement produces different output. Very nice! > Further consideration would be to use a block for output formating: > e.g. replace result \<\< [n] + a above to yield n, a and a block {|n,a| n > +a.join(’ ')} for string concatination etc Great, still more abstraction! 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 29, 2007, 6:45am UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/9 "2007-01-29T06:45:47Z")
How about recursive version? module Enumerable def cartprod(\*args) return self if [] == args b = args.shift result = [] self.each do |n| b.cartprod(\*args).each do |a| result \<\< [n] + (a.kind\_of?(Array)? a: [a]) end end result end end def cartprod(\*args) args.shift.cartprod(args) end Then both forms work as below: p (1…2).cartprod((3…5), (6…8)) p cartprod([1,2],[3,4,5],[6,7,8]) Further consideration would be to use a block for output formating: e.g. replace result \<\< [n] + a above to yield n, a and a block {|n,a| n +a.join(’ ')} for string concatination etc FYI, TJ ---
**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 29, 2007, 4:38pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/10 "2007-01-29T16:38:48Z")
On 2007/01/29, at 15:09, Trans wrote: > I’ll rename it to #cart and credit you. Can I suggest using the full name (#cartesian\_product) instead of short hand names? Paulo Jorge Duarte Köremoved\_email\_address@domain.invalid ---
**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 29, 2007, 6:57pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/11 "2007-01-29T18:57:55Z")
On 1/30/07, Trans [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > require ‘facets/core/enumerable/op\_pow’ > > [1,2] \*\* [3,4,5] > =\> [[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]] Confusing operand order… In set theory, e.g., [Set -- from Wolfram MathWorld](http://mathworld.wolfram.com/Set.html) the notation A^B, where A and B are arbitrary sets, is used to denote the set of maps from B to A. Then we get (a**b).size == (a.size)**(b.size) Gotoken ---
**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 29, 2007, 7:17pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/12 "2007-01-29T19:17:00Z")
On 1/29/07, Paulo Köch [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > On 2007/01/29, at 15:09, Trans wrote: > > > I’ll rename it to #cart and credit you. > > Can I suggest using the full name (#cartesian\_product) instead of > short hand names? yep and Ruby Q. #110 takes care of the rest ;). Seriously I back this demand with a potential alias #cart (or is this not the Facet philosophy?) Cheers Robert Paulo Jorge Duarte Köch ---
**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 29, 2007, 4:09pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/13 "2007-01-29T16:09:38Z")
On Jan 26, 6:05 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]] Hi– I was going to say that Facets has cross: require ‘facets/core/enumerable/cross’ Enumerable.cross([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]] Also when just deailing with a pair: require ‘facets/core/enumerable/op\_pow’ [1,2] \*\* [3,4,5] =\> [[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]] there are two considerations though: 1) your implementation retains an additional array level for each initial possibility. is that desired behavior? and 2) Facets’ implementation is poorly named conveying the cross product, which it is not, so unless someone has an objection, I’ll rename it to #cart and credit you. t. ([http://facets.rubyforge.org](http://facets.rubyforge.org)) ---
**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 29, 2007, 9:12pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/14 "2007-01-29T21:12:31Z")
On Jan 29, 10:09 am, “Trans” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > > result = [[]] > > end > > =\> [[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]] > > there are two considerations though: 1) your implementation retains an > additional array level for each initial possibility. is that desired > behavior? ignore that one, the layout of the result confused me. 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 29, 2007, 8:27pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/15 "2007-01-29T20:27:21Z")
On Jan 29, 1:15 pm, “Robert D.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > Seriously I back this demand with a potential alias #cart (or is this not > the Facet philosophy?) that’s doable. thanks. 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 29, 2007, 10:05pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/16 "2007-01-29T22:05:43Z")
“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): > there are two considerations though: 1) your implementation retains > an additional array level for each initial possibility. is that > desired behavior? I don’t yet understand what you mean. What’s the ``initial possibility’'? Do you want to say that I did waste CPU time for a needless loop execution? Which one? 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. 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 29, 2007, 11:56pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/17 "2007-01-29T23:56:07Z")
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): > > > there are two considerations though: 1) your implementation retains > > an additional array level for each initial possibility. is that > > desired behavior?I don’t yet understand what you mean. What’s the ``initial > > possibility’'? Do you want to say that I did waste CPU time for a > > needless loop execution? Which one? no no, i mis-read the output. it was a mistake on my part. sorry. > 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? but i mean to credit you with the name change, b/c you made me aware that my current name is a misnomer. 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 29, 2007, 9:15pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/18 "2007-01-29T21:15:32Z")
On Jan 29, 12:57 pm, “GOTO Kentaro” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > set of maps from B to A. Then we get (a**b).size == (a.size)**(b.size) > so maybe, i should probably get rid of that, maybe use it for actual > cross-product instead? 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 30, 2007, 6:32pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/19 "2007-01-30T18:32:25Z")
> 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? Yes please, The API and the efficiency are both important for a potential standard library, (so the name should be carefully choosen !) – Maurice ---
**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, 12:26pm UTC](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464/20 "2007-01-31T12:26:01Z")
On Jan 30, 11:07 am, “diam” [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? > > Yes please, > The API and the efficiency are both important for a potential standard > library, > (so the name should be carefully choosen !) > – Maurice Here ya go… require ‘generator’ module Enumerable class \<\< self ``` # Provides the cross-product of two or more Enumerables. # This is the class-level method. The instance method # calls on this. # # Enumerable.cross([1,2], [4], ["apple", "banana"]) # #=> [[1, 4, "apple"], [1, 4, "banana"], [2, 4, "apple"], [2, ``` 4, “banana”]] # # Enumerable.cross([1,2], [3,4]) # #=\> [[1, 3], [1, 4], [2, 3], [2, 4]] # #– # TODO Make a more efficient version just for Array (?) #++ ``` def cartesian_product(*enums, &block) raise if enums.empty? gens = enums.map{|e| Generator.new(e)} return [] if gens.any? {|g| g.end?} sz = gens.size res = [] tuple = Array.new(sz) loop do # fill tuple (0 ... sz).each { |i| tuple[i] = gens[i].current } if block.nil? res << tuple.dup else block.call(tuple.dup) end # step forward gens[-1].next (sz-1).downto(0) do |i| if gens[i].end? if i > 0 gens[i].rewind gens[i-1].next else return res end end end end #loop end alias :cart, :cartesian_product ``` end # The instance level version of Enumerable::cartesian\_product\. # # a = [] # [1,2].cart([4,5]){|elem| a \<\< elem } # a #=\> [[1, 4],[1, 5],[2, 4],[2, 5]] # #– # TODO Make a more efficient version just for Array (?) #++ def cart(\*enums, &block) Enumerable.cart(self, \*enums, &block) end alias :cart, :cartesian\_product end [Next page](https://www.ruby-forum.com/t/cartesian-product-of-arrays/83464.md?page=2)