Cartesian product of arrays


#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. removed_email_address@domain.invalid wrote/schrieb
removed_email_address@domain.invalid:

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. removed_email_address@domain.invalid wrote/schrieb removed_email_address@domain.invalid:

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. removed_email_address@domain.invalid wrote/schrieb removed_email_address@domain.invalid:

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. removed_email_address@domain.invalid wrote/schrieb
removed_email_address@domain.invalid:

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. removed_email_address@domain.invalid 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” removed_email_address@domain.invalid wrote/schrieb
removed_email_address@domain.invalid:

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öremoved_email_address@domain.invalid


#11

On 1/30/07, Trans removed_email_address@domain.invalid 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 (ab).size == (a.size)(b.size)

Gotoken


#12

On 1/29/07, Paulo Köch removed_email_address@domain.invalid 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. removed_email_address@domain.invalid 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” removed_email_address@domain.invalid 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.” removed_email_address@domain.invalid 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” removed_email_address@domain.invalid wrote/schrieb
removed_email_address@domain.invalid:

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. removed_email_address@domain.invalid wrote:

“Trans” removed_email_address@domain.invalid wrote/schrieb removed_email_address@domain.invalid:

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” removed_email_address@domain.invalid 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” removed_email_address@domain.invalid 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