Re: Multiple Combinatorics

[davido]

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?