Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a collection of a collection of numbers that I need to find the smallest number of groups to put them into whereas the distinct set of numbers in each set does not exceed a threshold. For example:

Collection A: 1,2,3
Collection B: 1,2,4,5
Collection C: 1,3,5,7,9
Collection D: 6,7,8,9,10,11
Threshold: 6

A valid solution would be:

Grouping 1: A,B {1,2,3,4,5}
Grouping 2: C   {1,3,5,7,9}
Grouping 3: D   {6,7,8,9,10,11}

Or

Grouping 1: B   {1,2,4,5}
Grouping 2: A,C {1,2,3,5,7,9}
Grouping 3: D   {6,7,8,9,10,11}

In my real problem the number of collections is 1000+ each with 50-300 numbers and my Threshold is 600. I am looking for the following.

  1. Is there a common mathematical name for this type of problem I can research.
  2. Is there a good approach to solving such a problem which results in the smallest number of Groupings.

Determining the affinity of 2 Collections is trivial (Union and compare vs each individual collection), but when I start to think about an arbitrary number of collections being grouped I can't seem to think of any non-brute force way to attacking the problem which would take a tremendous amount of time for a computer to solve after even 100 collections.

share|improve this question
    
Why would I merge A and B, or A and C here? What's your real problem? –  J. M. Dec 10 '11 at 1:42
1  
My real problem is determining optimal project mixes for a manufacturing line where I have a limited number of machine slots for parts and want to minimize feeder setup/machine programming per product. I want to throw a big pile of products into 1 end of my black box and out the other side comes the optimal product mix for which Part numbers to group together. There are other factors here but the crux of my problem is how to boil down my huge grouping permutations into a small list of promising options to run additional analysis against, like Qty of each type of part, part physical size, etc. –  deepee1 Dec 13 '11 at 16:27
    
This problem (the optimization problem) is NP-Hard. So the best algorithms you will get that run in polynomial time are approximations. Dynamic programming is usually a good place to start for problems like this. –  ml0105 Apr 9 at 13:37

1 Answer 1

If your sets were disjoint, you would have the classic bin packing problem. It appears when you group two sets you delete any duplicate elements. For the basic bin packing problem, there are heuristics (largest first, first fit) that have been proven not too far from optimal. You might start by looking for greatest overlap between your sets, as that reduces the number of items to put into bins.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.