Iterate over a cartesian product.

[Handy Gandy]

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?

 

[Andrew Wagner]

[Note: parts of this message were removed to make it a legal post.]

This thread seems to be a pretty thorough treatment of the idea:
http://www.ruby-forum.com/topic/95519 . It was the first result of a google
search on "ruby cross_product".

 

[Jörg W Mittag]

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

 

[Handy Gandy]

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

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

 

[Adam Prescott]

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])

 

[Adam Prescott]

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

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])

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

 

[Robert Klemme]

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?

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

This looks nice. How did you do the formatting?

If destruction is allowed, we can do:

irb(main):013:0> ary =3D [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
=3D> [[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]]
=3D> nil

Kind regards

robert

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Jörg W Mittag]

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]
   # => ]

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

 

[Robert Klemme]

Handy Gandy 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?
=A0 =A0ary =3D [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
=A0 =A0ary.first.product(*ary.drop(1))
=A0 =A0# =3D> [
=A0 =A0# =3D> =A0 [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9],
=A0 =A0# =3D> =A0 [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9],
=A0 =A0# =3D> =A0 [1, 5, 6], [1, 5, 7], [1, 5, 8], [1, 5, 9],
=A0 =A0# =3D> =A0 [2, 3, 6], [2, 3, 7], [2, 3, 8], [2, 3, 9],
=A0 =A0# =3D> =A0 [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9],
=A0 =A0# =3D> =A0 [2, 5, 6], [2, 5, 7], [2, 5, 8], [2, 5, 9]
=A0 =A0# =3D> ]

This looks nice. =A0How 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...

Though I assume Hirb or awesome_print could probably do it
automatically.

If destruction is allowed, we can do:

irb(main):013:0> ary =3D [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
=3D> [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
irb(main):014:0> pp ary.shift.product(*ary)
[[1, 3, 6],
...
=3D> 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 =3D arr.slice 0,1

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

irb(main):016:0> a=3D(1..5).to_a
=3D> [1, 2, 3, 4, 5]
irb(main):017:0> y=3D(x=3Da.dup).slice! 0,1
=3D> [1]
irb(main):018:0> x
=3D> [2, 3, 4, 5]
irb(main):019:0> a
=3D> [1, 2, 3, 4, 5]

Well, I guess the simplest approach is still

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

So we can do

irb(main):026:0> ary =3D [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
=3D> [[1, 2], [3, 4, 5], [6, 7, 8, 9]]
irb(main):027:0> x, *y =3D ary
=3D> [[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]]
=3D> nil



Kind regards

robert


--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/