Cartesian product of arrays

[Thomas_Hafner1 (Thomas Hafner)]

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

[Peter_Szinek3 (Peter Szinek)]

Thomas Hafner 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

[GOTO_Kentaro]

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
hope this helps,

gotoken

···

On 1/26/07, Thomas Hafner <thomas@hafner.nl.eu.org> wrote:

did I miss some standard library function? Anyway, then I'll do it on
my own:

[7rans]

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)

···

On Jan 26, 6:05 am, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:

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

[W_James]

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.

···

On Jan 26, 4:52 am, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:

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

[Thomas_Hafner1 (Thomas Hafner)]

Peter Szinek <peter@rubyrailways.com> wrote/schrieb <45B9E90C.7010106@rubyrailways.com>:

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

[Thomas_Hafner1 (Thomas Hafner)]

Peter Szinek <peter@rubyrailways.com> wrote/schrieb <45B9E90C.7010106@rubyrailways.com>:

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

[Paulo_Koch (Paulo Köch)]

Can I suggest using the full name (#cartesian_product) instead of short hand names?

Paulo Jorge Duarte Köch
paulo.koch@gmail.com

···

On 2007/01/29, at 15:09, Trans wrote:

I'll rename it to #cart and credit you.

[GOTO_Kentaro]

Confusing operand order...

In set theory, e.g., Set -- from Wolfram MathWorld
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

···

On 1/30/07, Trans <transfire@gmail.com> wrote:

  require 'facets/core/enumerable/op_pow'

  [1,2] ** [3,4,5]
  => [[1, 3], [1, 4], [1, 5], [2, 3], [2, 4], [2, 5]]

[7rans]

ignore that one, the layout of the result confused me.

T.

···

On Jan 29, 10:09 am, "Trans" <transf...@gmail.com> wrote:

On Jan 26, 6:05 am, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:

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

[Thomas_Hafner1 (Thomas Hafner)]

"Trans" <transfire@gmail.com> wrote/schrieb <1170083352.801941.114870@p10g2000cwp.googlegroups.com>:

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

[Thomas_Hafner1 (Thomas Hafner)]

"William James" <w_a_x_man@yahoo.com> wrote/schrieb <1170361559.491476.96660@p10g2000cwp.googlegroups.com>:

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

[Peter_Szinek3 (Peter Szinek)]

Thomas Hafner wrote:

Peter Szinek <peter@rubyrailways.com> wrote/schrieb <45B9E90C.7010106@rubyrailways.com>:

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

[Peter_Szinek3 (Peter Szinek)]

Thomas Hafner wrote:

Peter Szinek <peter@rubyrailways.com> wrote/schrieb <45B9E90C.7010106@rubyrailways.com>:

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

[Forum]

> 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 Quiz #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

···

On 1/29/07, Paulo Köch <paulo.koch@gmail.com> wrote:

On 2007/01/29, at 15:09, Trans wrote:
paulo.koch@gmail.com

--
"The best way to predict the future is to invent it."
- Alan Kay

[7rans]

so maybe, i should probably get rid of that, maybe use it for actual
cross-product instead?

t.

···

On Jan 29, 12:57 pm, "GOTO Kentaro" <goto...@gmail.com> wrote:

On 1/30/07, Trans <transf...@gmail.com> 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.,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)

[7rans]

"Trans" <transf...@gmail.com> wrote/schrieb <1170083352.801941.114...@p10g2000cwp.googlegroups.com>:

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

···

On Jan 29, 3:53 pm, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:

[W_James]

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

···

On Feb 2, 4:04 pm, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:

"William James" <w_a_x_...@yahoo.com> wrote/schrieb <1170361559.491476.96...@p10g2000cwp.googlegroups.com>:

> 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

[karoyakani]

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

···

On Jan 27, 10:14 am, Peter Szinek <p...@rubyrailways.com> wrote:

Thomas Hafner wrote:
> Peter Szinek <p...@rubyrailways.com> wrote/schrieb <45B9E90C.7010...@rubyrailways.com>:

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

[7rans]

that's doable. thanks.

t.

···

On Jan 29, 1:15 pm, "Robert Dober" <robert.do...@gmail.com> wrote:

On 1/29/07, Paulo Köch <paulo.k...@gmail.com> 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 Quiz #110 takes care of the rest ;).
Seriously I back this demand with a potential alias #cart (or is this not
the Facet philosophy?)