There's more than one way to do things PerlMonks

### Comment on

 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

In reply to Re: Multiple Combinatorics by davido
in thread Multiple Combinatorics by aartist

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?

Create A New User
Chatterbox?
and the universe expands...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (5)
As of 2018-06-21 03:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Should cpanminus be part of the standard Perl release?

Results (117 votes). Check out past polls.

Notices?