cartesian product of arrays

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

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.**--****.com/ 

Peter Szinek < XXXX@XXXXX.COM > wrote/schrieb < XXXX@XXXXX.COM >:


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

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.**--****.com/ 

Peter Szinek < XXXX@XXXXX.COM > wrote/schrieb < XXXX@XXXXX.COM >:


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

Exactly!

Cheers,
Peter

__
 http://www.**--****.com/ 

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

I wrote once like that. My product.rb is a mixin for enumerable.
 http://www.**--****.com/ ~gotoken/ruby/p/product/ruby-product-1.0.0.tar.gz
hope this helps,

gotoken

"karoyakani" < XXXX@XXXXX.COM > wrote/schrieb < XXXX@XXXXX.COM >:

                        ^^^^
    args.shift.cartprod(*args)
with the additional ``*'' would be better ...


... otherwise the second statement produces different output.
Very nice!


Great, still more abstraction!

Regards
  Thomas

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://www.**--****.com/ )

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

Paulo Jorge Duarte Kh
 XXXX@XXXXX.COM 

Confusing operand order...

In set theory, e.g.,  http://www.**--****.com/ 
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

that's doable. thanks.

t.

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

T.

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

t.