Velocity Reviews > Ruby > Combinatorics and permutations? Help?

# Combinatorics and permutations? Help?

David Palm
Guest
Posts: n/a

 03-11-2008
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 => [1_1, 1_2, ... , p1_x],
:input_prod_2 => [2_1, 2_1, ..., p2_y],
...
:input_prod_m => [m_1, m_1, ..., pm_z]
}

I need all the unique combinations of each product from the first group with each of the second. For example:
given: [ [1, 2], [3, p4] ]
I need to obtain: [ [1, 3], [1, 4], [2, 3], [2, 4] ]

Given: [ [1], [2, 3, 4] ]
I need: [ [1, 2], [1, 3], [1, 4] ]

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? :-/

Emmanuel Oga
Guest
Posts: n/a

 03-11-2008

Have Fun
--
Posted via http://www.ruby-forum.com/.

William James
Guest
Posts: n/a

 03-11-2008
On Mar 11, 5:06 am, David Palm <(E-Mail Removed)> wrote:

> I need all the unique combinations of each product from the first group with each of the second. For example:
> given: [ [1, 2], [3, p4] ]
> I need to obtain: [ [1, 3], [1, 4], [2, 3], [2, 4] ]
>
> Given: [ [1], [2, 3, 4] ]
> I need: [ [1, 2], [1, 3], [1, 4] ]

p [[1,2],[3,4]].inject([[]]){|old,lst|
lst.inject([]){|new,e| new + old.map{|c| c.dup << e}}}

David Palm
Guest
Posts: n/a

 03-11-2008
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.

Sergio Bayona
Guest
Posts: n/a

 02-08-2010
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/.

Jacob Mitchell
Guest
Posts: n/a

 02-08-2010
[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]]

Josh Cheek
Guest
Posts: n/a

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

On Sun, Feb 7, 2010 at 9:29 PM, Sergio Bayona <(E-Mail Removed)>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.

Sergio Bayona
Guest
Posts: n/a

 02-18-2010
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
> <(E-Mail Removed)>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/.