Iterate over a cartesian product.

H

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?
 
J

Jörg W Mittag

Handy said:
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
 
H

Handy Gandy

Handy said:
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.
 
A

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

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.
 
R

Robert Klemme

2010/9/14 J=F6rg W Mittag said:
Handy said:
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

Jörg W Mittag

Robert said:
2010/9/14 Jörg W Mittag said:
Handy said:
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
 
R

Robert Klemme

2010/9/15 J=F6rg W Mittag said:
Robert said:
2010/9/14 J=F6rg W Mittag said:
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/
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top