Just another Perl shrine  
PerlMonks 
Re: Multiple Combinatoricsby 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 nonoverlapping 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:
The run:
If overlaps between set A and set B are permitted, delete these three lines:
...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 bigO 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 Section
Seekers of Perl Wisdom

