Cartesian product of arrays

Ruby
1

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

2

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

3

Peter S. [email protected] wrote/schrieb
[email protected]:

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

4

Thomas H. wrote:

Peter S. [email protected] wrote/schrieb [email protected]:

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

5

Thomas H. wrote:

Peter S. [email protected] wrote/schrieb [email protected]:

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

6

Peter S. [email protected] wrote/schrieb
[email protected]:

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

7

On 1/26/07, Thomas H. [email protected] 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
hope this helps,

gotoken

8

“karoyakani” [email protected] wrote/schrieb
[email protected]:

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

9

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

10

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ö[email protected]

11

On 1/30/07, Trans [email protected] 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
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 (ab).size == (a.size)(b.size)

Gotoken

12

On 1/29/07, Paulo Köch [email protected] 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

13

On Jan 26, 6:05 am, Thomas H. [email protected] 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)

14

On Jan 29, 10:09 am, “Trans” [email protected] 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.

15

On Jan 29, 1:15 pm, “Robert D.” [email protected] wrote:

Seriously I back this demand with a potential alias #cart (or is this not
the Facet philosophy?)

that’s doable. thanks.

t.

16

“Trans” [email protected] wrote/schrieb
[email protected]:

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

17

On Jan 29, 3:53 pm, Thomas H. [email protected] wrote:

“Trans” [email protected] wrote/schrieb [email protected]:

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

18

On Jan 29, 12:57 pm, “GOTO Kentaro” [email protected] wrote:

set of maps from B to A. Then we get (ab).size == (a.size)(b.size)
so maybe, i should probably get rid of that, maybe use it for actual
cross-product instead?

t.

19

understood. actually i have a VERY fast implementation already that
was written by Michael Neuman. to be so fast it’s very ugly though :slight_smile:
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

20

On Jan 30, 11:07 am, “diam” [email protected] 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 :slight_smile:
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</

tt>.

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