Forum: Ruby cartesian product of arrays

8029153bbcbda4a6844440c93e0c6422?d=identicon&s=25 Thomas Hafner (Guest)
on 2007-01-26 12:05
(Received via mailing list)
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
F50f5d582d76f98686da34917531fe56?d=identicon&s=25 Peter Szinek (Guest)
on 2007-01-26 12:42
(Received via mailing list)
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.rubyrailways.com
8029153bbcbda4a6844440c93e0c6422?d=identicon&s=25 Thomas Hafner (Guest)
on 2007-01-26 13:41
(Received via mailing list)
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
F50f5d582d76f98686da34917531fe56?d=identicon&s=25 Peter Szinek (Guest)
on 2007-01-26 13:51
(Received via mailing list)
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.rubyrailways.com
8029153bbcbda4a6844440c93e0c6422?d=identicon&s=25 Thomas Hafner (Guest)
on 2007-01-27 19:06
(Received via mailing list)
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
F50f5d582d76f98686da34917531fe56?d=identicon&s=25 Peter Szinek (Guest)
on 2007-01-27 19:15
(Received via mailing list)
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.rubyrailways.com
662001fc95dd224902b4d5cfffc86e73?d=identicon&s=25 karoyakani (Guest)
on 2007-01-29 06:45
(Received via mailing list)
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
90bf8e8f068efd1ea80f9a66cc5cfac6?d=identicon&s=25 GOTO Kentaro (Guest)
on 2007-01-29 08:04
(Received via mailing list)
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/rub...
hope this helps,

gotoken
8029153bbcbda4a6844440c93e0c6422?d=identicon&s=25 Thomas Hafner (Guest)
on 2007-01-29 12:55
(Received via mailing list)
"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
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-29 16:09
(Received via mailing list)
On Jan 26, 6:05 am, Thomas Hafner <tho...@hafner.NL.EU.ORG> 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)
4e8d94859927eab3b50486d21249c068?d=identicon&s=25 Paulo Köch (Guest)
on 2007-01-29 16:38
(Received via mailing list)
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öchpaulo.koch@gmail.com
90bf8e8f068efd1ea80f9a66cc5cfac6?d=identicon&s=25 GOTO Kentaro (Guest)
on 2007-01-29 18:57
(Received via mailing list)
On 1/30/07, Trans <transfire@gmail.com> 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 (a**b).size == (a.size)**(b.size)


Gotoken
703fbc991fd63e0e1db54dca9ea31b53?d=identicon&s=25 Robert Dober (Guest)
on 2007-01-29 19:17
(Received via mailing list)
On 1/29/07, Paulo Köch <paulo.koch@gmail.com> 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 Quiz #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
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-29 20:27
(Received via mailing list)
On Jan 29, 1:15 pm, "Robert Dober" <robert.do...@gmail.com> wrote:
> Seriously I back this demand with a potential alias #cart (or is this not
> the Facet philosophy?)

that's doable. thanks.

t.
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-29 21:12
(Received via mailing list)
On Jan 29, 10:09 am, "Trans" <transf...@gmail.com> 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.
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-29 21:15
(Received via mailing list)
On Jan 29, 12:57 pm, "GOTO Kentaro" <goto...@gmail.com> wrote:
> 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.
8029153bbcbda4a6844440c93e0c6422?d=identicon&s=25 Thomas Hafner (Guest)
on 2007-01-29 22:05
(Received via mailing list)
"Trans" <transfire@gmail.com> wrote/schrieb
<1170083352.801941.114870@p10g2000cwp.googlegroups.com>:

> 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
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-29 23:56
(Received via mailing list)
On Jan 29, 3:53 pm, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:
> "Trans" <transf...@gmail.com> wrote/schrieb 
<1170083352.801941.114...@p10g2000cwp.googlegroups.com>:
>
> > 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 :-)
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.
3cd4f7d36b82a8160f448f8622fa4736?d=identicon&s=25 diam (Guest)
on 2007-01-30 18:32
(Received via mailing list)
> 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
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-31 12:26
(Received via mailing list)
On Jan 30, 11:07 am, "diam" <d...@ensta.fr> 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 :-)
> > 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 <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
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-31 16:04
(Received via mailing list)
On Jan 31, 6:25 am, "Trans" <transf...@gmail.com> wrote:
> > -- Maurice
>
> 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.
8029153bbcbda4a6844440c93e0c6422?d=identicon&s=25 Thomas Hafner (Guest)
on 2007-01-31 20:05
(Received via mailing list)
Hello,

"Trans" <transfire@gmail.com> wrote/schrieb
<1170111266.962275.227650@v45g2000cwv.googlegroups.com>:

> On Jan 29, 3:53 pm, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:
> > "Trans" <transf...@gmail.com> wrote/schrieb 
<1170083352.801941.114...@p10g2000cwp.googlegroups.com>:
> > 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?

I was curious enough to run both - my code and the one that you've
adapted from code by Michael Neuman - in irb, and my impression is,
that my code is even much faster. So if you're interested in providing
a really good library, please feel free to benchmark and chose the
best one according to your benchmark results.

Sorry that I did no benchmark myself (I'm still Ruby newbie); I just
run  (1..15).cartesian_product((1..15),(1..15))  with both variants.

In addition I don't find my implementation ugly, so there's a real
chance to get several advantages at the same time :-)

Regards
  Thomas
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-31 20:50
(Received via mailing list)
On Jan 31, 2:05 pm, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:
> > understood. actually i have a VERY fast implementation already that
> run  (1..15).cartesian_product((1..15),(1..15))  with both variants.
>
> In addition I don't find my implementation ugly, so there's a real
> chance to get several advantages at the same time :-)

Very good!!! I will do so then.

Thanks, and I'll let you know how it turns out.
T.
45196398e9685000d195ec626d477f0e?d=identicon&s=25 Trans (Guest)
on 2007-01-31 21:33
(Received via mailing list)
On Jan 31, 2:05 pm, Thomas Hafner <tho...@hafner.NL.EU.ORG> 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 :-)
> > want to see?
>
> I was curious enough to run both - my code and the one that you've
> adapted from code by Michael Neuman - in irb, and my impression is,
> that my code is even much faster. So if you're interested in providing
> a really good library, please feel free to benchmark and chose the
> best one according to your benchmark results.

Very Good! And you are quite right. I must have gotten this confused
with some other function. I've put you code in, and credited you.
Thanks lots for this! There was only one downside in that using the
block form couldn't run on the each possibility as it is computed, but
that's okay. I just tied the block into the end result:

def cartesian_product(*enums, &block)
      result = [[]]
      while [] != enums
        t, result = result, []
        b, *enums = enums
        t.each do |a|
          b.each do |n|
            result << a + [n]
          end
        end
      end
      if block_given?
        result.each{ |e| block.call(e) }
      else
        result
      end
    end

> Sorry that I did no benchmark myself (I'm still Ruby newbie); I just
> run  (1..15).cartesian_product((1..15),(1..15))  with both variants.
>
> In addition I don't find my implementation ugly, so there's a real
> chance to get several advantages at the same time :-)

Indeed! :-)

Thanks again,
T.
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 William James (Guest)
on 2007-02-01 21:31
(Received via mailing list)
On Jan 26, 4:52 am, Thomas Hafner <tho...@hafner.NL.EU.ORG> 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]]
>
> Regards
>   Thomas

Here's a shorter but slower way.

def cart_prod( *args )
  args.inject([[]]){|old,lst|
    lst.inject([]){|new,e|
      new + old.map{|c| c.dup << e}}}
end

Its results are ordered differently.
8029153bbcbda4a6844440c93e0c6422?d=identicon&s=25 Thomas Hafner (Guest)
on 2007-02-02 23:11
(Received via mailing list)
"William James" <w_a_x_man@yahoo.com> wrote/schrieb
<1170361559.491476.96660@p10g2000cwp.googlegroups.com>:

> Here's a shorter but slower way.
>
> def cart_prod( *args )
>   args.inject([[]]){|old,lst|
>     lst.inject([]){|new,e|
>       new + old.map{|c| c.dup << e}}}
> end

Wow, it's really short. Maybe it's not slower at all. Did you just
that? Or did you compare it actually?

Regards
  Thomas
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 William James (Guest)
on 2007-02-03 02:35
(Received via mailing list)
On Feb 2, 4:04 pm, Thomas Hafner <tho...@hafner.NL.EU.ORG> wrote:
> Wow, it's really short. Maybe it's not slower at all. Did you just
> that? Or did you compare it actually?
>
> Regards
>   Thomas


I tested it; it's slower.  This one isn't quite as slow.

def cart_prod( *args )
  args.inject([[]]){|old,lst|
    new = []
    lst.each{|e| new += old.map{|c| c.dup << e }}
    new
  }
end
C91098dc76d7ad473165ef24fe805312?d=identicon&s=25 Nanyang Zhan (xain)
on 2008-01-10 10:23
well, then can anyone tell me which one is the best?
15c44d9324a0bb97c550271a8131ad51?d=identicon&s=25 Adriano Mitre (amitre)
on 2009-07-26 23:39
Nanyang Zhan wrote:
> well, then can anyone tell me which one is the best?

Unfortunately, these methods uses too much memory, storing the whole
cartesian product Array in memory even its elements are needed only one
at a time. One nicer alternative is the Cartesian module:

"The Cartesian module provide methods for the calculation of the
cartesian producted between two enumberable objects. It can also be
easily mixed in into any enumberable class, i.e. any class with
Enumerable module mixed in."

The Cartesian module is available at
http://rubyforge.org/projects/cartesian/
15c44d9324a0bb97c550271a8131ad51?d=identicon&s=25 Adriano Mitre (amitre)
on 2009-07-26 23:40
Nanyang Zhan wrote:
> well, then can anyone tell me which one is the best?

Unfortunately, these methods use too much memory, storing the whole
cartesian product Array in memory even its elements are needed only one
at a time. A nicer alternative is the Cartesian module:

"The Cartesian module provide methods for the calculation of the
cartesian producted between two enumberable objects. It can also be
easily mixed in into any enumberable class, i.e. any class with
Enumerable module mixed in."

The Cartesian module is available at
http://rubyforge.org/projects/cartesian/
15c44d9324a0bb97c550271a8131ad51?d=identicon&s=25 Adriano Mitre (amitre)
on 2011-01-05 09:58
UPDATE: although gems releases are still being published at RubyForge
(and RubyGems), the cartesian project is now hosted at GitHub and its
new homepage is
http://adrianomitre.github.com/cartesian/website/index.html
Please log in before posting. Registration is free and takes only a minute.
Existing account

NEW: Do you have a Google/GoogleMail, Yahoo or Facebook account? No registration required!
Log in with Google account | Log in with Yahoo account | Log in with Facebook account
No account? Register here.