[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

cartesian product of arrays

Thomas Hafner

1/26/2007 10:52:00 AM

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

Peter Szinek

1/26/2007 11:43:00 AM

0

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

Thomas Hafner

1/26/2007 12:33:00 PM

0

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

Peter Szinek

1/26/2007 12:50:00 PM

0

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

Thomas Hafner

1/27/2007 5:56:00 PM

0

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

Peter Szinek

1/27/2007 6:15:00 PM

0

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

karoyakani

1/29/2007 5:45:00 AM

0

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

GOTO Kentaro

1/29/2007 7:04:00 AM

0

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:

I wrote once like that. My product.rb is a mixin for enumerable.
http://www.notwork.org/~gotoken/ruby/p/product/ruby-product-1....
hope this helps,

gotoken

Thomas Hafner

1/29/2007 11:43:00 AM

0

"karoyakani" <tj.takei@gmail.com> wrote/schrieb <1170049485.669713.169350@h3g2000cwc.googlegroups.com>:

> 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

1/29/2007 3:09:00 PM

0



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

Paulo Köch

1/29/2007 3:38:00 PM

0


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öch
paulo.koch@gmail.com