Perl Monk, Perl Meditation PerlMonks

Re: Multiple Combinatorics

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

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?

Dave

Create A New User
Node Status?
node history
Node Type: note [id://965142]
help
Chatterbox?
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
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (230 votes). Check out past polls.

Notices?