cartesian product - next to last version

Discussion in 'Ruby' started by walter a kehowski, Aug 11, 2005.

  1. Hello,

    Since the original thread got a little long, I decided to post my next to
    last version in a new thread. My previous version gave results like
    [[1,4],7] for more than two arrays when you really wanted [1,4,7]. The trick
    is to flatten each element of the product. The following works for any
    number of arrays. Of course you might want a product in which the elements
    of that product are arrays. Any suggestions?

    class Array

    def cartprod(b=[])
    if b.empty? then
    #assume self an array of arrays
    inject {|cp,x| cp.cartprod(x) }
    else
    z = inject([]) {|a,x| b.inject(a) {|a,y| a << [x,y]}}
    z.collect! {|x| x.flatten }
    end
    end

    end


    a=[1,2,3]
    b=[4,5,6]
    c=[7,8,9]

    # works fine
    p [a,b,c].cartprod

    # doesn't work since [1,4,7,[10,11]] is [1,4,7,10,11]
    d=[10, [11,12]]
    p [a,b,c,d].cartprod
     
    walter a kehowski, Aug 11, 2005
    #1
    1. Advertising

  2. On 11/08/05, walter a kehowski <> wrote:
    > Hello,
    >=20
    > Since the original thread got a little long, I decided to post my next to
    > last version in a new thread. My previous version gave results like
    > [[1,4],7] for more than two arrays when you really wanted [1,4,7]. The tr=

    ick
    > is to flatten each element of the product. The following works for any
    > number of arrays. Of course you might want a product in which the element=

    s
    > of that product are arrays. Any suggestions?
    >=20
    > class Array
    >=20
    > def cartprod(b=3D[])
    > if b.empty? then
    > #assume self an array of arrays
    > inject {|cp,x| cp.cartprod(x) }
    > else
    > z =3D inject([]) {|a,x| b.inject(a) {|a,y| a << [x,y]}}
    > z.collect! {|x| x.flatten }
    > end
    > end
    >=20
    > end
    >=20
    >=20
    > a=3D[1,2,3]
    > b=3D[4,5,6]
    > c=3D[7,8,9]
    >=20
    > # works fine
    > p [a,b,c].cartprod
    >=20
    > # doesn't work since [1,4,7,[10,11]] is [1,4,7,10,11]
    > d=3D[10, [11,12]]
    > p [a,b,c,d].cartprod
    >=20
    >=20
    >=20
    >=20


    Here is my stab at the problem (I made it as a standalone method, as I
    don't think of this operation as something that an array can do:

    require 'test/unit'

    def cartprod(base, *others)
    return base.map{|a| [a] } if others.empty?
    others =3D cartprod(*others)
    base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, *b]) } }
    end

    class CarprodTest < Test::Unit::TestCase
    def test_simple
    assert_equal([[1, 'a'], [1, 'b'],=20
    =09=09 [2, 'a'], [2, 'b'],=20
    =09=09 [3, 'a'], [3, 'b']],=20
    =09=09 cartprod([1,2,3], %w(a b)),=20
    'Simple Cartesian Product failed')
    assert_equal([[1, "a"], [1, "b"], [1, "c"],=20
    [2, "a"], [2, "b"], [2, "c"],=20
    =09=09 [3, "a"], [3, "b"], [3, "c"]],
    =09=09 cartprod(1..3, 'a'..'c'),
    'Simple Cartesian Product with ranges failed')
    end
    =20
    def test_multiple
    assert_equal([[1, 'a', :A], [1, 'a', :B], [1, 'b', :A], [1, 'b', :B],=
    =20
    =09=09 [2, 'a', :A], [2, 'a', :B], [2, 'b', :A], [2, 'b', :B]],=20
    =09=09 cartprod([1,2], %w(a b), [:A, :B]),=20
    'Multiple Cartesian Product failed')
    end

    def test_array
    assert_equal([[1, ["a", "a"]], [1, ["b", "b"]],=20
    [2, ["a", "a"]], [2, ["b", "b"]],=20
    =09=09 [3, ["a", "a"]], [3, ["b", "b"]]],
    cartprod(1..3, [%w(a a), %w(b b)]),
    =09=09 'Cartesian Product with arrays failed')
    end

    def test_base_cases
    assert_equal([], cartprod([]), "Base case empty array is not correct")
    assert_equal([[1], [2], [3]], cartprod(1..3), "Base case single
    array is not correct")
    end
    end

    regards,

    Brian

    --=20
    http://ruby.brian-schroeder.de/

    Stringed instrument chords: http://chordlist.brian-schroeder.de/
     
    Brian Schröder, Aug 11, 2005
    #2
    1. Advertising

  3. --Apple-Mail-1--567785806
    Content-Transfer-Encoding: 7bit
    Content-Type: text/plain;
    charset=US-ASCII;
    delsp=yes;
    format=flowed

    On Aug 11, 2005, at 5:06 AM, walter a kehowski wrote:
    > Of course you might want a product in which the elements
    > of that product are arrays. Any suggestions?


    In such cases, I use the Vector class (require 'matrix') as the
    'atomic' unit. Then Array#flatten doesn't peek inside the Vectors and
    flatten them inappropriately.
    --Apple-Mail-1--567785806--
     
    Gavin Kistner, Aug 11, 2005
    #3
  4. >
    > In such cases, I use the Vector class (require 'matrix') as the
    > 'atomic' unit. Then Array#flatten doesn't peek inside the Vectors and
    > flatten them inappropriately.
    >


    require 'matrix'
    # see page 694 of PR
    #

    class Array

    def cartprod(b=[])

    if b.empty? then
    #assume self an array of arrays
    z=inject {|cp,x| cp.cartprod(x) }
    else
    z = inject([]) {|a,x| b.inject(a) {|a,y| a << [x,y]}}
    z.collect! {|x| x.flatten }
    end
    end

    end

    #Everything works
    a=[1,2]
    b=[4,5]
    c=[7,8]
    p [a,b,c].cartprod

    d=[10, Vector[11,12]]
    p [a,b,c,d].cartprod
     
    walter a kehowski, Aug 11, 2005
    #4
  5. walter a kehowski

    Dave Burt Guest

    Brian Schröder offered:
    > def cartprod(base, *others)
    > return base.map{|a| [a] } if others.empty?
    > others = cartprod(*others)
    > base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
    > *b]) } }
    > end


    Wow - that's nice and functional!

    My procedural solution is much uglier, but it 1) isn't recursive and 2)
    yields results to a given block as it iterates.

    If given a block, the following will return nil, but pass the values into a
    given block:

    a=[[1,2,3],[4,5,6],[7,8,9]]
    a.cartprod do |a0e, a1e, a2e|
    # ...
    end

    class Array
    def cartprod

    unless block_given?
    ret = []
    cartprod {|tuple| ret << tuple}
    return ret
    end
    return if any? {|a| a.size == 0 }
    index = [0] * size
    begin
    yield *zip(index).map {|a| a[0][a[1]] }
    (index.size - 1).downto(0) do |i|
    if index < self.size - 1
    index += 1
    break
    else
    index = 0
    end
    end
    end while index != [0] * size
    end
    end

    Cheers,
    Dave
     
    Dave Burt, Aug 12, 2005
    #5
  6. On 12/08/05, Dave Burt <> wrote:
    > Brian Schr=F6der offered:
    > > def cartprod(base, *others)
    > > return base.map{|a| [a] } if others.empty?
    > > others =3D cartprod(*others)
    > > base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
    > > *b]) } }
    > > end

    >=20
    > Wow - that's nice and functional!
    >=20
    > My procedural solution is much uglier, but it 1) isn't recursive and 2)
    > yields results to a given block as it iterates.
    >=20
    > If given a block, the following will return nil, but pass the values into=

    a
    > given block:
    >=20
    > a=3D[[1,2,3],[4,5,6],[7,8,9]]
    > a.cartprod do |a0e, a1e, a2e|
    > # ...
    > end
    >=20
    > class Array
    > def cartprod
    >=20
    > unless block_given?
    > ret =3D []
    > cartprod {|tuple| ret << tuple}
    > return ret
    > end
    > return if any? {|a| a.size =3D=3D 0 }
    > index =3D [0] * size
    > begin
    > yield *zip(index).map {|a| a[0][a[1]] }
    > (index.size - 1).downto(0) do |i|
    > if index < self.size - 1
    > index +=3D 1
    > break
    > else
    > index =3D 0
    > end
    > end
    > end while index !=3D [0] * size
    > end
    > end
    >=20
    > Cheers,
    > Dave
    >=20
    >=20
    >=20
    >=20


    Yielding the values is certainly a good idea, but it makes the code a
    lot bigger. Anyhow, here is the recursive, yielding version.

    def cartprod(base, *others)
    if block_given?
    if others.empty?
    base.each{|a| yield [a]} =20
    else
    base.each do | a |
    =09cartprod(*others) do | b |
    =09 yield [a, *b]=20
    =09end
    end
    end
    nil
    else
    return base.map{|a|[a]} if others.empty?
    others =3D cartprod(*others)
    base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, *b]) }=
    }
    end
    end


    --=20
    http://ruby.brian-schroeder.de/

    Stringed instrument chords: http://chordlist.brian-schroeder.de/
     
    Brian Schröder, Aug 12, 2005
    #6
  7. On 12/08/05, Brian Schr=F6der <> wrote:
    > On 12/08/05, Dave Burt <> wrote:
    > > Brian Schr=F6der offered:
    > > > def cartprod(base, *others)
    > > > return base.map{|a| [a] } if others.empty?
    > > > others =3D cartprod(*others)
    > > > base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
    > > > *b]) } }
    > > > end

    > >
    > > Wow - that's nice and functional!
    > >
    > > My procedural solution is much uglier, but it 1) isn't recursive and 2)
    > > yields results to a given block as it iterates.
    > >
    > > If given a block, the following will return nil, but pass the values in=

    to a
    > > given block:
    > >
    > > a=3D[[1,2,3],[4,5,6],[7,8,9]]
    > > a.cartprod do |a0e, a1e, a2e|
    > > # ...
    > > end
    > >
    > > class Array
    > > def cartprod
    > >
    > > unless block_given?
    > > ret =3D []
    > > cartprod {|tuple| ret << tuple}
    > > return ret
    > > end
    > > return if any? {|a| a.size =3D=3D 0 }
    > > index =3D [0] * size
    > > begin
    > > yield *zip(index).map {|a| a[0][a[1]] }
    > > (index.size - 1).downto(0) do |i|
    > > if index < self.size - 1
    > > index +=3D 1
    > > break
    > > else
    > > index =3D 0
    > > end
    > > end
    > > end while index !=3D [0] * size
    > > end
    > > end
    > >
    > > Cheers,
    > > Dave
    > >
    > >
    > >
    > >

    >=20
    > Yielding the values is certainly a good idea, but it makes the code a
    > lot bigger. Anyhow, here is the recursive, yielding version.
    >=20
    > def cartprod(base, *others)
    > if block_given?
    > if others.empty?
    > base.each{|a| yield [a]}
    > else
    > base.each do | a |
    > cartprod(*others) do | b |
    > yield [a, *b]
    > end
    > end
    > end
    > nil
    > else
    > return base.map{|a|[a]} if others.empty?
    > others =3D cartprod(*others)
    > base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a, *b])=

    } }
    > end
    > end
    >=20
    >=20


    I've got some interesting benchmark results to share:
    Benchmark.bm(35) do | b |=20
    [[2, 16], [6,7], [25,4], [800,2]].each do | size, depth |
    args =3D Array.new(depth) { Array.new(size) {|i| i} } =20
    b.report("Recursive Array (#{size}**#{depth})") do cartprod(*args) end
    b.report("Recursive Array iterated (#{size}**#{depth})") do
    cartprod(*args).each do | e | end end
    b.report("Recursive Yielding (#{size}**#{depth})") do
    cartprod_y(*args) do | e | end end
    b.report("Procedural Yielding (#{size}**#{depth})") do
    args.cartprod do | *e | end end
    puts
    end
    end

    user system total =
    real
    Recursive Array (2**16) 0.610000 0.130000 0.740000 ( 0.84=
    0845)
    Recursive Array iterated (2**16) 0.890000 0.130000 1.020000 ( 1.28=
    7632)
    Recursive Yielding (2**16) 3.910000 0.760000 4.670000 ( 4.77=
    9378)
    Procedural Yielding (2**16) 4.850000 0.890000 5.740000 ( 5.84=
    7342)

    Recursive Array (6**7) 1.690000 0.310000 2.000000 ( 2.02=
    7407)
    Recursive Array iterated (6**7) 2.300000 0.430000 2.730000 ( 2.72=
    1382)
    Recursive Yielding (6**7) 5.830000 1.330000 7.160000 ( 7.16=
    6822)
    Procedural Yielding (6**7) 11.200000 1.970000 13.170000 ( 13.44=
    0081)

    Recursive Array (25**4) 1.750000 0.360000 2.110000 ( 2.11=
    8353)
    Recursive Array iterated (25**4) 1.990000 0.510000 2.500000 ( 2.50=
    7274)
    Recursive Yielding (25**4) 9.130000 1.050000 10.180000 ( 10.22=
    0420)
    Procedural Yielding (25**4) 12.020000 2.120000 14.140000 ( 15.58=
    0462)

    Recursive Array (800**2) 3.750000 0.630000 4.380000 ( 4.37=
    5153)
    Recursive Array iterated (800**2) 3.050000 0.790000 3.840000 ( 3.83=
    9810)
    Recursive Yielding (800**2) 5.380000 0.930000 6.310000 ( 6.30=
    8811)
    Procedural Yielding (800**2) 17.170000 2.480000 19.650000 ( 20.67=
    6642)



    In these benchmarks the recursive version is a lot faster. Beware that
    only creating and discarding the block is not a good measure,
    therefore I also included an iteration about the returned array for
    the array method. As you see it depends on the characteristics of the
    argument which method is fastest.

    regards,

    Brian
    --=20
    http://ruby.brian-schroeder.de/

    Stringed instrument chords: http://chordlist.brian-schroeder.de/
     
    Brian Schröder, Aug 12, 2005
    #7
  8. walter a kehowski

    Dave Burt Guest

    Interesting benchmarks. Thanks for sharing these and your code, Brian.

    I was initially surprised that your recursive code was quicker than my
    procedural, but when you look at them, it's obvious that my code is just
    doing more, unnecessarily, while yours is nice and simple.

    Any tips on learning to write code like your 3-line functonal recursive
    cartprod?

    Cheers,
    Dave
     
    Dave Burt, Aug 12, 2005
    #8
  9. On 12/08/05, Dave Burt <> wrote:
    > Interesting benchmarks. Thanks for sharing these and your code, Brian.
    >=20
    > I was initially surprised that your recursive code was quicker than my
    > procedural, but when you look at them, it's obvious that my code is just
    > doing more, unnecessarily, while yours is nice and simple.
    >=20
    > Any tips on learning to write code like your 3-line functonal recursive
    > cartprod?
    >=20
    > Cheers,
    > Dave
    >=20


    Thanks Dave,

    regarding the tips you requested. The only thing that helps is to
    think about how to split the problem recursively. It is like an
    inductive proof. So it helps to make lots of inductive proofs
    throughout your studies and get into a mindset for this. Then the
    solution comes naturally. All a matter of experience I suppose (Though
    I don't have that much, there are lots of more experienced people
    here.)
    Sorry if that is not of much help, maybe thinking about the proposed
    solutions in this thread and the other threads will be more of a help.

    best regards,

    Brian

    --=20
    http://ruby.brian-schroeder.de/

    Stringed instrument chords: http://chordlist.brian-schroeder.de/
     
    Brian Schröder, Aug 12, 2005
    #9
  10. Hello,

    Yielding the values is certainly a good idea, but it makes the code a
    lot bigger. Anyhow, here is the recursive, yielding version.

    def cartprod(base, *others)
    if block_given?
    if others.empty?
    base.each{|a| yield [a]}
    else
    base.each do | a |
    cartprod(*others) do | b |
    yield [a, *b]
    end
    end
    end
    nil # <--Why?
    else
    return base.map{|a|[a]} if others.empty?
    others = cartprod(*others)
    base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
    *b]) } }
    end
    end

    --
    http://ruby.brian-schroeder.de/

    ## Question: Why the nil?
     
    walter a kehowski, Aug 12, 2005
    #10
  11. walter a kehowski

    Dave Burt Guest

    Thanks, Brian.
     
    Dave Burt, Aug 13, 2005
    #11
  12. On 12/08/05, walter a kehowski <> wrote:
    > Hello,
    >=20
    > Yielding the values is certainly a good idea, but it makes the code a
    > lot bigger. Anyhow, here is the recursive, yielding version.
    >=20
    > def cartprod(base, *others)
    > if block_given?
    > if others.empty?
    > base.each{|a| yield [a]}
    > else
    > base.each do | a |
    > cartprod(*others) do | b |
    > yield [a, *b]
    > end
    > end
    > end
    > nil # <--Why?
    > else
    > return base.map{|a|[a]} if others.empty?
    > others =3D cartprod(*others)
    > base.inject([]) { | r, a | others.inject(r) { | r, b | r << ([a,
    > *b]) } }
    > end
    > end
    >=20
    > ## Question: Why the nil?
    >=20


    because otherwise the function would return the base array when
    invoked with a block. And that would not make any sense for method
    chaining. Nil will invoke an exception if a chained method is called
    upon it.

    regards,

    Brian



    --=20
    http://ruby.brian-schroeder.de/

    Stringed instrument chords: http://chordlist.brian-schroeder.de/
     
    Brian Schröder, Aug 13, 2005
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. deancoo

    cartesian product...

    deancoo, Feb 28, 2005, in forum: C++
    Replies:
    4
    Views:
    2,323
    Matt Bitten
    Feb 28, 2005
  2. Cartesian product

    , Feb 11, 2007, in forum: C++
    Replies:
    2
    Views:
    975
    Kai-Uwe Bux
    Feb 11, 2007
  3. Thorsten Kampe

    Cartesian Product of two lists (itertools)

    Thorsten Kampe, Jan 25, 2009, in forum: Python
    Replies:
    3
    Views:
    432
    Mark Wooding
    Jan 26, 2009
  4. Brad
    Replies:
    9
    Views:
    371
  5. walter a kehowski

    cartesian product

    walter a kehowski, Aug 7, 2005, in forum: Ruby
    Replies:
    26
    Views:
    333
    tony summerfelt
    Aug 10, 2005
Loading...

Share This Page