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.