Assign groups of indistinguishable objects to groups of unique objects of a set size

Question

The problem: Given multiple groups, of varying size, of indistinguishable objects, arrange them into groups of a given size in such a way that all of the following are satisfied:

• Each group created contains only unique objects
• The number of groups created is maximized

Ex: Suppose you are given the following groups of marbles

{blue: 5, yellow: 3, black: 1, red: 2, white: 4}

Possible groups (n=4) that could be created are

[blue, yellow, black, white]
[blue, red, white, yellow]
[blue, yellow, red, white]

My question is: Is there an algorithm to create these groups in such a way that we can guarantee that the number of groups created is maximized?

Answer 1

Let $m$ be the total number of objects. Suppose you try to form $k$ groups, with $m-nk$ items left over. Define the "excess" of each color to be the number of objects in that color minus $k$, with the convention that the excess is zero when this difference is negative. In your example, with $k=3$, the excesses are

{blue: 2, yellow: 0, black: 0, red: 0, white: 1}

Since there are $k$ groups, at most $k$ marbles of each color can be put into groups. The excesses will comprise the $m-nk$ leftover marbles. Therefore, in order for it to be possible to form $k$ groups, the sum of the excesses must be at most $m-nk$.

Conversely, if condition is fulfilled, the it possible to form $k$ groups. Remove all of the excess items, so at most $k$ items in each color remain. Place the remaining items in a line so that each color appears together as a group. Go down the line and assign each item to a group between $1$ and $k$ by counting $1,2,\dots,k,1,2,\dots,k\dots$ The only way this could fail was if two objects of the same color were assigned the same number. However, we already ensured there were at most $k$ objects in each color, this cannot happen.

In your example, when $k=3$, the sum of the excesses is $2+0+0+0+1=3$, which is at most $15-4\cdot 3=3$. Therefore, you can put the objects into $3$ groups, as follows.

B B B Y Y Y K R R W W W    B B W   
1 2 3 1 2 3 1 2 3 1 2 3    Excess

Groups: 
1: [B, Y, K, W]
2: [B, Y, R, W]
3: [B, Y, R, W]

Therefore, the algorithm to maximize the number of groups is this:

1. Set $k=\lfloor m/n\rfloor$.

2. Compute the sum of the excesses, and see if it is at most $m-nk.$

3. If it is not, decrement $k$ and go to step $2$.

4. Form $k$ groups using the process described.