cartesian product

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

  1. Hello,

    How would I create a function that will take list (array) of integers and
    return their cartesian product?

    Thank You,

    Walter Kehowski
    nuby
    walter a kehowski, Aug 7, 2005
    #1
    1. Advertising

  2. > How would I create a function that will take list (array) of integers and
    > return their cartesian product?


    You could do something like:

    a =3D [1, 2, 3]

    b =3D []

    a.each do |elementone|
    a.each do |elementtwo|
    b << [elementone, elementtwo]
    end
    end

    That should do the trick (I haven't tested it though)
    Giovanni Intini, Aug 7, 2005
    #2
    1. Advertising

  3. "Giovanni Intini" <> wrote in message
    news:...
    > How would I create a function that will take list (array) of integers and
    > return their cartesian product?


    >You could do something like:
    >
    >a = [1, 2, 3]
    >
    >b = []
    >
    >a.each do |elementone|
    > a.each do |elementtwo|
    > b << [elementone, elementtwo]
    > end
    >end
    >
    >That should do the trick (I haven't tested it though)


    Giovanni,

    Yes, that works. Another nuby question: How to make it a function? Such as
    cartprod(a,b) returning c?

    Walter
    walter a kehowski, Aug 7, 2005
    #3
  4. "Giovanni Intini" <> wrote in message
    news:...
    Remember that in Ruby you seldom have standalone functions. You should
    probably create a class that has the cartprod method.

    Giovanni,

    Here's what I have so far:

    def cartprod(a,b)

    c=[]

    a.each do |ae|
    b.each do |be|
    c << [ae, be]
    end
    end

    return c

    end

    a=[1,2,3]

    b=[4,5,6]

    c=cartprod(a,b)

    c.each { |ce| print ce,"\n" }

    and this does print all the elements of c. Great. Now how do I do a class?
    Can I create a new method for Array?

    Walter Kehowski
    walter a kehowski, Aug 7, 2005
    #4
  5. Remember that in Ruby you seldom have standalone functions. You should
    probably create a class that has the cartprod method.
    Giovanni Intini, Aug 7, 2005
    #5
  6. walter a kehowski

    daz Guest

    walter a kehowski wrote:
    >
    >
    > Here's what I have so far:
    >
    Code:
    >
    > and this does print all the elements of c.
    > Great. Now how do I do a class?
    > Can I create a new method for Array?
    >[/color]
    
    
    class Array
    def cartprod(b)
    c=[]
    each do |ae|
    b.each do |be|
    c << [ae, be]
    end
    end
    c
    end
    end
    
    a=[1,2,3]
    b=[4,5,6]
    
    c = a.cartprod(b)
    
    c.each { |ce| p ce }
    
    
    daz
    daz, Aug 7, 2005
    #6
  7. if you want to create a new method for array just do

    class Array
    def cartprod(ary)
    result =3D []
    self.each do |ae|
    ary.each do |be|
    result << [ae, be]
    end
    end
    result
    end
    end

    this way you can have an array and do new_array =3D
    source_array.cartprod(other_array)
    Giovanni Intini, Aug 7, 2005
    #7
  8. walter a kehowski <> wrote:
    > "Giovanni Intini" <> wrote in message
    > news:...
    > Remember that in Ruby you seldom have standalone functions. You should
    > probably create a class that has the cartprod method.
    >
    > Giovanni,
    >
    > Here's what I have so far:
    >
    > def cartprod(a,b)
    >
    > c=[]
    >
    > a.each do |ae|
    > b.each do |be|
    > c << [ae, be]
    > end
    > end
    >
    > return c
    >
    > end
    >
    > a=[1,2,3]
    >
    > b=[4,5,6]
    >
    > c=cartprod(a,b)
    >
    > c.each { |ce| print ce,"\n" }
    >
    > and this does print all the elements of c. Great. Now how do I do a
    > class? Can I create a new method for Array?
    >
    > Walter Kehowski


    Note that it might be more memory efficient to write a iteration method:

    def cartprod(a,b)
    a.each {|ae| b.each {|be| yield ae, be}}
    end

    Then you can also do this if needed

    c=[]
    cartprod(a,b) {|x,y| c << [x,y]}

    If you just need every combination once the iteration approach is more
    efficient.

    Kind regards

    robert
    Robert Klemme, Aug 7, 2005
    #8
  9. Robert Klemme <> wrote:
    >
    > Note that it might be more memory efficient to write a iteration method:
    >
    > def cartprod(a,b)
    > a.each {|ae| b.each {|be| yield ae, be}}
    > end
    >
    > Then you can also do this if needed
    >
    > c=[]
    > cartprod(a,b) {|x,y| c << [x,y]}
    >
    > If you just need every combination once the iteration approach is more
    > efficient.


    Or even better,

    if block_given?
    yield ae, be
    else
    (c ||= []) << ae, be
    end

    martin
    Martin DeMello, Aug 7, 2005
    #9
  10. walter a kehowski

    Randy Kramer Guest

    On Sunday 07 August 2005 10:51 am, Martin DeMello wrote:
    > if block_given?
    > yield ae, be
    > else
    > (c ||= []) << ae, be
    > end


    I'm sure you know what you're talking about, but I wonder how many others
    will, even with comments. (Maybe I just need to go back to Pascal?)

    Randy Kramer
    Randy Kramer, Aug 7, 2005
    #10
  11. walter a kehowski

    Hal Fulton Guest

    Randy Kramer wrote:
    > On Sunday 07 August 2005 10:51 am, Martin DeMello wrote:
    >
    >>if block_given?
    >> yield ae, be
    >>else
    >> (c ||= []) << ae, be
    >>end

    >
    >
    > I'm sure you know what you're talking about, but I wonder how many others
    > will, even with comments. (Maybe I just need to go back to Pascal?)


    Haha... if it's this line you have trouble with

    (c ||= []) << ae, be

    it's not that hard.

    The ||= is a well-known idiom -- same as c = c || [] here. Basically
    "assign c this value, unless it is already non-nil."

    So then you have either an existing array or an empty one.
    Then you can append (<<) onto it.

    If it's the yield that bothers you, just study a bit more
    Ruby. Pascal was wonderful in 1980 -- unless you already knew
    something better -- but I'm content to let it go now. ;)


    Hal
    Hal Fulton, Aug 7, 2005
    #11
  12. walter a kehowski

    Randy Kramer Guest

    On Sunday 07 August 2005 01:22 pm, Hal Fulton wrote:
    > Haha... if it's this line you have trouble with
    >
    > (c ||= []) << ae, be
    >
    > it's not that hard.
    >
    > The ||= is a well-known idiom -- same as c = c || [] here. Basically
    > "assign c this value, unless it is already non-nil."
    >
    > So then you have either an existing array or an empty one.
    > Then you can append (<<) onto it.


    Hal,

    Thanks--that line was the most confusing. (Yield I at least have a clue about,
    though I would need to think about it in this context a little more.)

    regards,

    Randy Kramer

    >
    > If it's the yield that bothers you, just study a bit more
    > Ruby. Pascal was wonderful in 1980 -- unless you already knew
    > something better -- but I'm content to let it go now. ;)
    >
    >
    > Hal
    Randy Kramer, Aug 7, 2005
    #12
  13. Hello,

    Here's what I have so far, combining the previous suggestions of Robert
    Klemme and Martin DeMello:

    class Array

    def cartprod(a,b)
    a.each {|ae|
    b.each {|be|
    if block_given?
    yield ae,be
    else
    (c ||= []) << ae,be
    end
    end

    end #Array

    However,

    c=cartprod([1,2,3],[4,5,6])

    c.each { |ce| print ce,"\n" }

    gives the following syntax error:

    cartprod.rb:24: syntax error
    (c ||= []) << ae,be
    ^
    cartprod.rb:26: syntax error
    cartprod.rb:132: syntax error

    and I would like to take the cartesian product of an arbitrary number of
    sets in the most elegant way.
    walter a kehowski, Aug 7, 2005
    #13
  14. Hello,

    The following is not in the spirit of previous comments

    class Array

    def cartprod(b)

    c=[]
    each {|ae| b.each {|be| c << [ae, be] } }
    c.collect! {|ce| ce.flatten}

    end #cartprod

    end #Array

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

    c=a[0]
    as=a.slice(1..a.length-1)
    as.each {|ase| c=c.cartprod(ase) }
    c.each {|ce| ce.each {|x| print x," " }; print "\n" }

    Would the following be desirable? If cartprod has two or more arguments, do
    the usual thing, but if it has just one, it takes the cartesian product with
    that argument, i.e, cartprod(a) gives cartprod(a,a) or a.cartprod(a), etc.

    And thanks for all the suggestion so far. I usually just play around with
    Perl but got $#@% fatigue. It was a toss-up between Python and Ruby so here
    I am.

    Walter Kehowski
    walter a kehowski, Aug 7, 2005
    #14
  15. walter a kehowski

    Dave Burt Guest

    walter a kehowski wrote...
    > cartprod.rb:24: syntax error
    > (c ||= []) << ae,be
    > ^
    > cartprod.rb:26: syntax error
    > cartprod.rb:132: syntax error


    class Array
    def cartprod(b)
    each do |ae|
    b.each do |be|
    if block_given?
    yield ae, be # <-- you can yield multiple objects
    else
    (c ||= []) << [ae, be] # <-- you need to put (ae, be) in a
    single
    # object (i.e. an array) to put in an
    array
    end
    end # <-- you had missed 2 closing braces (line 132 error)
    end
    c # <-- you want to return this if no block was given
    end
    end

    Cheers,
    Dave
    Dave Burt, Aug 7, 2005
    #15
  16. walter a kehowski

    Dave Burt Guest

    walter a kehowski...
    > c=[]
    > each {|ae| b.each {|be| c << [ae, be] } }
    > c.collect! {|ce| ce.flatten}


    Flatten is going to squash nested arrays. Maybe:

    inject([]) {|c, ae| c.concat b.map {|be| [ae, be] } }

    >
    > c=a[0]
    > as=a.slice(1..a.length-1)


    You can do this (in Perl, too):
    as = a.slice(1..-1)
    or this:
    as = a[1..-1]

    > as.each {|ase| c=c.cartprod(ase) }
    > c.each {|ce| ce.each {|x| print x," " }; print "\n" }
    >
    > Would the following be desirable? If cartprod has two or more arguments,
    > do the usual thing, but if it has just one, it takes the cartesian product
    > with that argument, i.e, cartprod(a) gives cartprod(a,a) or a.cartprod(a),
    > etc.


    I wouldn't. Typing an extra argument makes the function clearer - cartesian
    product is a two-array function.

    > And thanks for all the suggestion so far. I usually just play around with
    > Perl but got $#@% fatigue. It was a toss-up between Python and Ruby so
    > here I am.


    You're welcome.

    Cheers,
    Dave
    Dave Burt, Aug 7, 2005
    #16
  17. Hello,

    If one defines

    class Array
    def cartprod(b)
    each do |ae|
    b.each do |be|
    if block_given?
    yield ae, be
    else
    (c ||= []) << [ae, be]
    end
    end
    end
    c
    end
    end

    then

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

    c=cartpord(a.slice(0..-1))

    c.each {|ce| ce.each {|x| print x," " }; print "\n" }

    gives the error

    cartprod.rb:45: undefined method `cartpord' for main:Object (NoMethodError)

    and

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

    c=a[0]

    b=a.slice(1..-1)

    b.each{|be| c=c.cartprod(be) }

    c.each {|ce| ce.each {|x| print x," " }; print "\n" }

    gives the error

    cartprod.rb:24:in `cartprod': undefined local variable or method `c' for [1,
    2, 3]:Array (NameError)
    from cartprod.rb:49
    from cartprod.rb:49:in `each'
    from C:/Documents and Settings/walter/My Documents/cartprod.rb:49

    and, finally,

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

    c=cartprod(a)

    c.each {|ce| ce.each {|x| print x," " }; print "\n" }

    gives the error

    cartprod.rb:45: undefined method `cartprod' for main:Object (NoMethodError)

    Well, I'm clearly plying around trying to get it JUST RIGHT.

    Walter Kehowski
    walter a kehowski, Aug 8, 2005
    #17
  18. walter a kehowski

    Dave Burt Guest

    Walter,

    One error is mine, two are yours.

    > c=cartpord(a.slice(0..-1))
    > ...
    > cartprod.rb:45: undefined method `cartpord' for main:Object
    > (NoMethodError)


    You've got a typo here (or -> ro). Also, cartprod is defined as a method of
    Arrays, so you can't use it as a function like that.

    > b.each{|be| c=c.cartprod(be) }
    > ...
    > cartprod.rb:24:in `cartprod': undefined local variable or method `c' for
    > [1, 2, 3]:Array (NameError)
    > from cartprod.rb:49
    > from cartprod.rb:49:in `each'
    > from C:/Documents and Settings/walter/My Documents/cartprod.rb:49


    This is a bug in my untested code. It occurs because c is not defined
    outside the inner block. This version will actually work (I've renamed c to
    prod):

    class Array
    def cartprod(b)
    prod = ([] unless block_given?)
    each do |ae|
    b.each do |be|
    if block_given?
    yield ae, be
    else
    prod << [ae, be]
    end
    end
    end
    prod
    end
    end

    > c=cartprod(a)
    > ...
    > cartprod.rb:45: undefined method `cartprod' for main:Object
    > (NoMethodError)


    Again, cartprod has to be used on an array, like this:

    a=[[1,2,3],[4,5,6],[7,8,9]]
    b=a.shift
    a.each do |ae|
    b = b.cartprod(ae)
    # the following line is so you don't get [[[1,4],7], [[1,4],8] ...
    b.map! {|be| be.flatten } if b[0][0].is_a? Array
    end
    b #=> [[1, 4, 7], [1, 4, 8] ... [3, 6, 9]] #(27 elements)

    But if you want to cartesianly-multiply multiple arrays, maybe you want
    something more like this:

    class Array
    def cartprod
    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

    This will return nil, but pass the values you want into a given block:

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

    You should easily be able to change it to return an array if you need to.

    Cheers,
    Dave
    Dave Burt, Aug 8, 2005
    #18
  19. walter a kehowski

    Gene Tani Guest

  20. walter a kehowski <> wrote:
    >
    > cartprod.rb:24: syntax error
    > (c ||= []) << ae,be
    > ^
    > cartprod.rb:26: syntax error
    > cartprod.rb:132: syntax error


    My mistake, sorry. Should be (c ||= []) << [ae, be]

    > and I would like to take the cartesian product of an arbitrary number of
    > sets in the most elegant way.


    Define a cartprod2 that takes the cartesian product of two arrays.
    Define base cases sensibly - cartprod2([], a) = a.map {|i| } and
    cartprod2(a,b) = a.each {|i| b.each {|j| c << i.concat(j)}}

    Use that as a helper function for cartprod thus:

    def cartprod(*arrays)
    arrays.inject([]) {|prod, ary| cartprod2(prod, ary)}
    end

    Untested, but that's the general idea.

    martin
    Martin DeMello, Aug 8, 2005
    #20
    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,278
    Matt Bitten
    Feb 28, 2005
  2. Cartesian product

    , Feb 11, 2007, in forum: C++
    Replies:
    2
    Views:
    944
    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:
    404
    Mark Wooding
    Jan 26, 2009
  4. Brad
    Replies:
    9
    Views:
    345
  5. walter a kehowski

    cartesian product - next to last version

    walter a kehowski, Aug 11, 2005, in forum: Ruby
    Replies:
    11
    Views:
    201
    Brian Schröder
    Aug 13, 2005
Loading...

Share This Page