Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Comment on

( #3333=superdoc: 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


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!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • 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:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others rifling through the Monastery: (9)
    As of 2015-07-06 11:53 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









      Results (73 votes), past polls