Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation

Re: Multiple Combinatorics

by davido (Archbishop)
on Apr 15, 2012 at 08:46 UTC ( #965142=note: print w/replies, xml ) Need Help??

in reply to Multiple Combinatorics

I hope I'm understanding the problem. Regardless, it was an interesting puzzle (and a great question).

I understand you to be saying that you want all possible merges of the combinations of set A with the combinations of set B. And I think that by mentioning the potential for overlap you're saying that any merge that would result in an overlap should be disqualified. I don't think it is sufficient to just generate all combinations of set A, and all combinations of set B, merge, and shuffle. That would not result in a result set of all possible non-overlapping merges.

My solution creates all possible combinations of set A (3 at a time), and then iterates over that list in an outer loop while merging all possible combinations of set B (taken 2 at a time) that don't result in an overlap of any elements. The implementation sacrifices speed efficiency in favor of memory efficiency; we never actually hold onto any full list of combinations of either set A or set B. We just use the iterators for each set. That means that the set B combination object will be created and destroyed on every iteration from set A.

Here's the code:

use strict; use warnings; use Math::Combinatorics; use List::Util qw( first ); my @A = 'A' .. 'Z'; my @B = 0 .. 9; my $count = 0; my $comb_A = Math::Combinatorics->new( count => 3, data => [@A] ); while( my @combo_A = $comb_A->next_combination ) { my $comb_B = Math::Combinatorics->new( count => 2, data => [@B] ); INNER: while( my @combo_B = $comb_B->next_combination ) { my %overlap; @overlap{@combo_B} = (); next INNER if first{ exists $overlap{$_} } @combo_A; print join( ' ', @combo_A, @combo_B ), "\n"; $count++; } } print "Whew, that resulted in $count result-producing iterations!\n";

The run:

A B C 0 1 A B C 0 2 A B C 0 3 A B C 0 4 A B C 0 5 A B C 0 6 ... ... ... X Y Z 7 6 X Y Z 4 0 X Y Z 4 3 X Y Z 4 6 X Y Z 0 3 X Y Z 0 6 X Y Z 3 6 Whew, that resulted in 117000 result-producing iterations!

If overlaps between set A and set B are permitted, delete these three lines:

my %overlap; @overlap{@combo_B} = (); next INNER if first{ exists $overlap{$_} } @combo_A;

...and if I totally missed the boat I'm anxious to see a correct interpretation and the resulting solution code! :)

Update: In the update to your original post, and further clarified in a message to me, I see that you may be needing to merge multiple sets of combinations (ie, more than just two). I don't see any solution that doesn't involve diving deeper and deeper into nested loops, driving your big-O complexity higher with each additional set of combinations.

Is this just one way of approaching a more general problem that you're trying to solve?


Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://965142]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (6)
As of 2018-01-21 19:34 GMT
Find Nodes?
    Voting Booth?
    How did you see in the new year?

    Results (230 votes). Check out past polls.