# Iterate over a cartesian product

**URL:** <https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968>\
**Category:** Ruby\
**Created:** [September 14, 2010, 3:55pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968 "2010-09-14T15:55:51Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 14, 2010, 3:55pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/1 "2010-09-14T15:55:51Z")

</div>

I have an array of N arrays A\_i: [A\_1,A\_2,…,A\_N].

I want to iterate over the cartesian product A\_1xA\_2…xA\_N.

Is there a simple way of doing this without specifying N?

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 14, 2010, 4:11pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/2 "2010-09-14T16:11:40Z")

</div>

This thread seems to be a pretty thorough treatment of the idea:  
[Cartesian product of arrays - Ruby - Ruby-Forum](http://www.ruby-forum.com/topic/95519) . It was the first result of a  
google  
search on “ruby cross\_product”.

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 14, 2010, 5:15pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/3 "2010-09-14T17:15:30Z")

</div>

Handy G. wrote:

> I have an array of N arrays A\_i: [A\_1,A\_2,…,A\_N].
> 
> I want to iterate over the cartesian product A\_1xA\_2…xA\_N.
> 
> Is there a simple way of doing this without specifying N?

```
ary = [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
ary.first.product(*ary.drop(1))
# => [
# => [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9],
# => [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9],
# => [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9],
# => [2, 3, 6], [2, 3, 7], [2, 3, 8], [2, 3, 9],
# => [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9],
# => [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9]
# => ]

```

jwm

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 14, 2010, 7:33pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/4 "2010-09-14T19:33:06Z")

</div>

On Tue, 14 Sep 20 10 17:13:11 +0200, Jörg W Mittag wrote:

> ```
> # => [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9], # => [1, 4, 6],
> [1, 4, 7], [1, 4, 8], [1, 4, 9], # => [1, 5, 6], [1, 5, 7], [1, 5,
> 8], [1, 5, 9], # => [2, 3, 6], [2, 3, 7], [2, 3, 8], [2, 3, 9], #
> => [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], # => [2, 5, 6],
> [2, 5, 7], [2, 5, 8], [2, 5, 9] # => ]
> 
> ```
> 
> jwm

That looks so cool I wish I knew what it does.

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 14, 2010, 10:41pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/5 "2010-09-14T22:41:36Z")

</div>

ary.first is the first element of ary.  
ary.product(one, two, …) is the cartesian product of ary with its  
arguments.  
ary.drop(1) is ary[1…-1], all the elements of ary but the first.  
ary.product(\*ary.drop(1)) passes each element of ary[1…-1] to  
product() as an argument, making it equivalent to

ary.product(ary[1], ary[2], …, ary[-1])

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 14, 2010, 10:44pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/6 "2010-09-14T22:44:32Z")

</div>

Whoops, that should be ary.first.product, of course.

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 15, 2010, 10:44am UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/7 "2010-09-15T10:44:25Z")

</div>

2010/9/14 Jörg W Mittag [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> # =\> [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9],
> 
> # =\> [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9],
> 
> # =\> [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9],
> 
> # =\> [2, 3, 6], [2, 3, 7], [2, 3, 8], [2, 3, 9],
> 
> # =\> [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9],
> 
> # =\> [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9]
> 
> # =\> ]

This looks nice. How did you do the formatting?

If destruction is allowed, we can do:

irb(main):013:0\> ary = [[1, 2], [3, 4, 5], [6, 7, 8, 9]]  
=\> [[1, 2], [3, 4, 5], [6, 7, 8, 9]]  
irb(main):014:0\> pp ary.shift.product(\*ary)  
[[1, 3, 6],  
[1, 3, 7],  
[1, 3, 8],  
[1, 3, 9],  
[1, 4, 6],  
[1, 4, 7],  
[1, 4, 8],  
[1, 4, 9],  
[1, 5, 6],  
[1, 5, 7],  
[1, 5, 8],  
[1, 5, 9],  
[2, 3, 6],  
[2, 3, 7],  
[2, 3, 8],  
[2, 3, 9],  
[2, 4, 6],  
[2, 4, 7],  
[2, 4, 8],  
[2, 4, 9],  
[2, 5, 6],  
[2, 5, 7],  
[2, 5, 8],  
[2, 5, 9]]  
=\> nil

Kind regards

robert

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 15, 2010, 1:52pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/8 "2010-09-15T13:52:19Z")

</div>

Robert K. wrote:

> > Â Â # =\> Â [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9],  
> > Â Â # =\> Â [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9],  
> > Â Â # =\> Â [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9],  
> > Â Â # =\> Â [2, 3, 6], [2, 3, 7], [2, 3, 8], [2, 3, 9],  
> > Â Â # =\> Â [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9],  
> > Â Â # =\> Â [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9]  
> > Â Â # =\> ]  
> > This looks nice. How did you do the formatting?

By hand 🙂

Though I assume Hirb or awesome\_print could probably do it  
automatically.

> If destruction is allowed, we can do:
> 
> irb(main):013:0\> ary = [[1, 2], [3, 4, 5], [6, 7, 8, 9]]  
> =\> [[1, 2], [3, 4, 5], [6, 7, 8, 9]]  
> irb(main):014:0\> pp ary.shift.product(\*ary)  
> [[1, 3, 6],  
> …  
> =\> nil

That’s nice. Having toyed with Scala and Haskell, mutation just feels  
_so_ dirty to me. I guess I need some re-education to get back into  
the idiomatic Ruby mindset.

jwm

---

<div class="post-metadata">

**Author:** ![Handy\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/h/3ab097/32.png) [@Handy\_G](https://www.ruby-forum.com/u/Handy_G)\
**Post date:** [September 15, 2010, 2:16pm UTC](https://www.ruby-forum.com/t/iterate-over-a-cartesian-product/194968/9 "2010-09-15T14:16:55Z")

</div>

2010/9/15 Jörg W Mittag [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> > > # =\> [
> > > 
> > > # =\> [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9],
> > > 
> > > # =\> [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9],
> > > 
> > > # =\> [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9],
> > > 
> > > # =\> [2, 3, 6], [2, 3, 7], [2, 3, 8], [2, 3, 9],
> > > 
> > > # =\> [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9],
> > > 
> > > # =\> [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9]
> > > 
> > > # =\> ]
> > 
> > This looks nice. How did you do the formatting?
> 
> By hand 🙂

14:09:29 ~$ gem19 install ‘By hand’  
ERROR: could not find gem By hand locally or in a repository  
14:09:58 ~$

Hm…

> > =\> nil
> 
> That’s nice. Having toyed with Scala and Haskell, mutation just feels  
> _so_ dirty to me. I guess I need some re-education to get back into  
> the idiomatic Ruby mindset.

Unfortunately there is no #slice which has two return values. If  
there was we could do

a,b = arr.slice 0,1

But we can do this to achieve the same (i.e. non destructively  
partitioning):

irb(main):016:0\> a=(1…5).to\_a  
=\> [1, 2, 3, 4, 5]  
irb(main):017:0\> y=(x=a.dup).slice! 0,1  
=\> [1]  
irb(main):018:0\> x  
=\> [2, 3, 4, 5]  
irb(main):019:0\> a  
=\> [1, 2, 3, 4, 5]

Well, I guess the simplest approach is still

irb(main):001:0\> a=(1…5).to\_a  
=\> [1, 2, 3, 4, 5]  
irb(main):002:0\> x,\*y = a  
=\> [1, 2, 3, 4, 5]  
irb(main):003:0\> x  
=\> 1  
irb(main):004:0\> y  
=\> [2, 3, 4, 5]

So we can do

irb(main):026:0\> ary = [[1, 2], [3, 4, 5], [6, 7, 8, 9]]  
=\> [[1, 2], [3, 4, 5], [6, 7, 8, 9]]  
irb(main):027:0\> x, \*y = ary  
=\> [[1, 2], [3, 4, 5], [6, 7, 8, 9]]  
irb(main):028:0\> pp x.product(\*y)  
[[1, 3, 6],  
[1, 3, 7],  
[1, 3, 8],  
[1, 3, 9],  
[1, 4, 6],  
[1, 4, 7],  
[1, 4, 8],  
[1, 4, 9],  
[1, 5, 6],  
[1, 5, 7],  
[1, 5, 8],  
[1, 5, 9],  
[2, 3, 6],  
[2, 3, 7],  
[2, 3, 8],  
[2, 3, 9],  
[2, 4, 6],  
[2, 4, 7],  
[2, 4, 8],  
[2, 4, 9],  
[2, 5, 6],  
[2, 5, 7],  
[2, 5, 8],  
[2, 5, 9]]  
=\> nil

🙂

Kind regards

robert