I am facing the following combination problem :
I do have $B$ colored boxes, each one containing $N_b$ balls of the given color. The total number of balls is thus $\sum_{b=1}^{B} N_b = N$.
I want to distribute the balls to P players with the two following aims:
- The number of balls received by each player must be the same (ie $N/P$)
- The sum of the number of different colors hold by each player must be minimal : if each player get $c_p$ different colors, I want $\sum_{p=1}^{P} c_p$ as small as possible.
Is there any formulae or algorithm to respect both constraints ?
Edit
What is this problem useful ?
This problem arises eg in scientific computing : you have a available number of processus ($P$) and you want to perform arithmetics on several ($B$) arrays of different sizes ($N_b$). Obviously you want the arrays to be uniformly distributed (otherwise one process will have much more work and will slow the whole procedure), but you also want to minimize the splits in the original arrays since each one implies a communication between processus, which are also time consuming.
What to start with :
I guess we can easily fall back to the case of a distribution $\tilde D=\{\tilde N_1, \tilde N_2, ... \tilde N_{B}\}$ to distribute on P' players, with $P' \le P$ and $\tilde N_b < N/P$ : indeed, any boxe in the original distribution having more than $N/P$ ball will fill up 100% capacity of one (or more) player. We can then try to do pairs (or triplets, etc.) with the remaining boxes to reach N/P, but we may not have a perfect match without cuts in the general case.