How would an algorithm that splits/sorts numbers into three groups to make them equally large work?

Question

I have to write an algorithm to split/sort numbers into three groups to make them equally large.

To be more specific:

I have three groups, let's call them A, B and C. Then I have a lot of numbers. Each number has assigned a group to which it belongs, but the thing is, that one number could belong to one of two or one of three groups (to one of them, but we don't know exactly to which one).

Sample data:

Number | Group 
1      | A (this number HAVE TO be in group A) 
2      | A 
3      | B 
4      | C 
5      | AC (this number can be in group A or C) 
6      | BC (can be in group B or C) 
7      | A 
8      | B 
9      | ABC (can be in group A, B or C) 
... 

One of the correct results of this sample can be:

A: 1, 2, 7 
B: 3, 8, 9 
C: 4, 5, 6 

It doesn't matter which group is chosen if there were multiple groups assigned to one number (it would be best if it is chosen randomly). The goal is to split those numbers to make each group equally large (or as close to it as possible).

My question is: How would you write algorithm to achieve the desired result? Pseudo code or verbal description is enough.

Answer 1

Keep track of the size of each of the subgroups and when there's one that is ambiguous place it in the subgroup with the lowest current count.

If you want to go for even closer accuracy, place all singletons in their respective sub-groups (all non-ambiguous values). And then do a second pass for all that fit in 2 sub-groups, and a third for all that fit in 3 sub-groups, at most this would be an O(n^2) operation anyway, with the previous one running in O(n*log(n)) roughly. Just based off of what I'm seeing in my head.

If you split the main array into 3 sub-arrays with 1, 2, and 3 group values being in their own respective arrays (if space isn't an issue) you could perform the second in nearly O(n*log(n)).

Answer 2

I think this is something on the line of an Exact Cover Problem. At least the solution should be possible with similar approaches like Knuth' Algorithm X and Dancing Links.

It's a type of Constraint Satisfaction Problem or at least similar to it. Your constraints here are the rules that the numbers must fulfill, belonging to one of the groups and the groups adding up as similar as possible.

You could solve this with a kind of Depth First Search, since you need to compare all results (though you could stop the search in case you find a grouping where all groups have exactly equal sums and can't get better)

First step: Assign those numbers that can belong only to a single group and forget about them.

Then take the first number that has two options. Choose the first option and proceed with the next number in the same way. Repeat until all numbers are assigned and remember the sums of the groups.

Then go back one step with the last number and assign the number to the next possible group. If this was the last possible group, go back one more number, assign this to the next possible group and proceed again with the last number.

That way you get a search tree that traverses all possible combinations.

Though this would use a lot of memory in case you have many numbers.

(In so far it's not an exact cover problem, since there is not necessarily an exact solution.)