cartesian product of arrays

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

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

 

[Thomas Hafner]

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

 

[Peter Szinek]

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

 

[Thomas Hafner]

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

 

[Peter Szinek]

Does that follow your suggestion?:

Exactly!

Cheers,
Peter

__
http://www.rubyrailways.com

 

[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

 

[GOTO Kentaro]

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

 

[Thomas Hafner]

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

 

[Trans]

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

 

[Paulo Köch]

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

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

Paulo Jorge Duarte K=F6ch
(e-mail address removed)

 

[GOTO Kentaro]

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)


Gotoken

 

[Trans]

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

that's doable. thanks.

t=2E

 

[Trans]

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?

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

T.

 

[Trans]

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)

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

t.

 

[Thomas Hafner]

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

 

[Trans]

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.

 

[diam]

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?

Yes please,
The API and the efficiency are both important for a potential standard
library,
(so the name should be carefully choosen !)
-- Maurice

 

[Trans]

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 = gens.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.end?
if i > 0
gens.rewind
gens[i-1].next
else
return res
end
end
end
end #loop
end

alias :cart, :cartesian_product
end


# The instance level version of <tt>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

 

[Trans]

Here ya go....

Err... fix the alias bug though (damn no-comma gets me every time!),
and the last def should be using the full name, ie. "def
cartesian_product".

T.