Combinatorics and permutations? Help?

Discussion in 'Ruby' started by David Palm, Mar 11, 2008.

  1. David Palm

    David Palm Guest

    Hi,
    I have a problem involving combinatorics and permutations and my brain hurts.

    The problem: I have a hash of products in input. I then build an array of equivalent products for each input product. I end up with an array such as this:
    {
    :input_prod_1 => [:p1_1, :p1_2, ... , p1_x],
    :input_prod_2 => [:p2_1, :p2_1, ..., p2_y],
    ...
    :input_prod_m => [:pm_1, :pm_1, ..., pm_z]
    }

    I need all the unique combinations of each product from the first group with each of the second. For example:
    given: [ [:p1, :p2], [:p3, p4] ]
    I need to obtain: [ [:p1, :p3], [:p1, :p4], [:p2, :p3], [:p2, :p4] ]

    Given: [ [:p1], [:p2, :p3, :p4] ]
    I need: [ [:p1, :p2], [:p1, :p3], [:p1, :p4] ]

    The number of input products is in the order of tens (max); the same goes for the number of equivalent products. This means the total number of partitions is pretty large and I need to weed out the equivalent ones soon/fast enough to reduce the total number.

    I've been making attempts with the permutation gem all morning; looks like it's doing the "right thing", but frankly my maths skills are lacking and I can't really figure out how to use it (should I?).

    Also: order is not important for the result arrays.

    This is easy, right? :-/
     
    David Palm, Mar 11, 2008
    #1
    1. Advertising

  2. David Palm

    Emmanuel Oga Guest

    Emmanuel Oga, Mar 11, 2008
    #2
    1. Advertising

  3. On Mar 11, 5:06 am, David Palm <> wrote:

    > I need all the unique combinations of each product from the first group with each of the second. For example:
    > given: [ [:p1, :p2], [:p3, p4] ]
    > I need to obtain: [ [:p1, :p3], [:p1, :p4], [:p2, :p3], [:p2, :p4] ]
    >
    > Given: [ [:p1], [:p2, :p3, :p4] ]
    > I need: [ [:p1, :p2], [:p1, :p3], [:p1, :p4] ]


    p [[1,2],[3,4]].inject([[]]){|old,lst|
    lst.inject([]){|new,e| new + old.map{|c| c.dup << e}}}
     
    William James, Mar 11, 2008
    #3
  4. David Palm

    David Palm Guest

    On Tue, 11 Mar 2008 20:40:11 +0900, William James wrote:
    > p [[1,2],[3,4]].inject([[]]){|old,lst|
    > lst.inject([]){|new,e| new + old.map{|c| c.dup << e}}}


    awesome. Totally rocks.
     
    David Palm, Mar 11, 2008
    #4
  5. I have a similar challenge:

    given: [{"a" => [1, 2]}, {"b" => [3, 4]}]

    I need: [{"a" => 1, "b" => 3}, {"a" => 1, "b" => 4}, {"a" => 2, "b" =>
    3}, {"a" => 2, "b" => 4}]

    Any ideas?

    Thanks.
    S
    --
    Posted via http://www.ruby-forum.com/.
     
    Sergio Bayona, Feb 8, 2010
    #5
  6. [Note: parts of this message were removed to make it a legal post.]

    >
    > given: [{"a" => [1, 2]}, {"b" => [3, 4]}]
    >
    > I need: [{"a" => 1, "b" => 3}, {"a" => 1, "b" => 4}, {"a" => 2, "b" =>
    > 3}, {"a" => 2, "b" => 4}]
    >
    > Any ideas?
    >
    > Yup, the following method does nearly the same thing, except it takes

    arrays. You could either use this method for inspiration, or convert your
    desired input into my array of arrays input format and then convert the
    output back to your desired format. Hope that helps.

    def selections(arrays, results=[Array.new])
    return results if arrays.empty?

    new_selection_choices = arrays.shift
    results_with_new_selections = []

    results.each do |prev_selection_set|
    new_selection_choices.each do |selection|
    results_with_new_selections <<
    prev_selection_set.clone.push(selection)
    end
    end

    return selections(arrays, results_with_new_selections)
    end

    selections([[1, 2], [3, 4]]) #=> [[1, 3], [1, 4], [2, 3], [2, 4]]
     
    Jacob Mitchell, Feb 8, 2010
    #6
  7. David Palm

    Josh Cheek Guest

    [Note: parts of this message were removed to make it a legal post.]

    On Sun, Feb 7, 2010 at 9:29 PM, Sergio Bayona <>wrote:

    > I have a similar challenge:
    >
    > given: [{"a" => [1, 2]}, {"b" => [3, 4]}]
    >
    > I need: [{"a" => 1, "b" => 3}, {"a" => 1, "b" => 4}, {"a" => 2, "b" =>
    > 3}, {"a" => 2, "b" => 4}]
    >
    > Any ideas?
    >
    > Thanks.
    > S
    > --
    > Posted via http://www.ruby-forum.com/.
    >
    >

    Here is a solution I have come up with (http://gist.github.com/297937). I
    don't know how you want all edge cases to be handled, I made my best
    guesses, you can see them in the tests.
     
    Josh Cheek, Feb 8, 2010
    #7
  8. Sorry took so long to respond. Your solution worked as expected. Thanks!

    SB

    Josh Cheek wrote:
    > On Sun, Feb 7, 2010 at 9:29 PM, Sergio Bayona
    > <>wrote:
    >
    >> S
    >> --
    >> Posted via http://www.ruby-forum.com/.
    >>
    >>

    > Here is a solution I have come up with (http://gist.github.com/297937).
    > I
    > don't know how you want all edge cases to be handled, I made my best
    > guesses, you can see them in the tests.


    --
    Posted via http://www.ruby-forum.com/.
     
    Sergio Bayona, Feb 18, 2010
    #8
    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. Carnosaur

    combinatorics question

    Carnosaur, Oct 28, 2003, in forum: C Programming
    Replies:
    17
    Views:
    567
    Carnosaur
    Oct 31, 2003
  2. Xah Lee

    [perl-python] combinatorics fun

    Xah Lee, Feb 10, 2005, in forum: Python
    Replies:
    7
    Views:
    401
    bruno modulix
    Feb 11, 2005
  3. Nic

    Python and Combinatorics

    Nic, May 16, 2006, in forum: Python
    Replies:
    4
    Views:
    1,744
    Gerard Flanagan
    May 16, 2006
  4. none

    Python and Combinatorics

    none, Oct 24, 2007, in forum: Python
    Replies:
    4
    Views:
    528
    Gerard Flanagan
    Oct 26, 2007
  5. Michael Robertson

    Combinatorics

    Michael Robertson, Feb 12, 2008, in forum: Python
    Replies:
    12
    Views:
    932
    Paul Hankin
    Feb 13, 2008
Loading...

Share This Page