Forming n disjoint sets based on limited (but very useful) information.

67 Views Asked by At

I am a computer scientist, and I have written an algorithm that works with graphs. The long and short of it is, I arrive at a point where I have k sets, each has unique values within them. The sets vary in size.

So maybe I have 8 sets: three are size 1, two are size 2, two are size 4, and one of them is size 9.

I have to separate these k sets into n sets, where n is a value that is fixed ahead of time. Let's say n is 18.

Well, using basic math I can see that I have 3+4+8+9 = 24 values to work with. 24/18 = 1.3333.. average values per set, in order to form n sets.

Now here is where things get tough. The k sets are formed as such because they are disjoint, and the values must remain disjoint. This means that each set of size one, must remain size one. In a similar fashion, any of the other sets cannot be "mixed" with values from another set. So, sets of size two could never form a new set of size 3. Nor could a value from the set of size 9 be put into a set with a value from a set of size 4 to form a set of size 2. Essentially, values can only form a new set with other values they were originally matched with.

Using this information, is it possible to actually solve what the sizes of my n disjoint sets must be?

DISCLAIMER: The above example is not a real example and likely does not have an actual solution. If needed, I could run my algorithm to get a real world example.

quick clarification: all values in my sets must be used.

1

There are 1 best solutions below

1
On BEST ANSWER

In your example you showed the average refined part size (sets that make up the partition are often called parts) is $1 \frac13$, so the most equal-sized arrangements will consist of one- and two-subsets contained in the original parts.

Knowing how many disjoint subsets you want to end up with, I'd start with the biggest original parts and break them into subsets of size equal to the ceiling of the average size, together with any "remainder" size pieces. Stop if and when you have the desired number $n$ of disjoint subsets, including any you've not split yet.

If making a first pass of this kind does not produce enough subsets, continue by splitting some of them into smaller pieces, until you have enough.