110 people divided into 3 groups of different sizes

Question

I need to distribute 110 people to 3 groups of different sizes as follows:
50 people to group 1
40 people to group 2
20 people to group 3

Instead of simply filling each group up to the desired size and then moving on to the next group, the distribution should happen in a "balanced" manner, so that

#1 -> group 1
#2 -> group 1
#3 -> group 1
#4 -> group 2
#5 -> group 2
#4 -> group 3
#5 -> group 1
#6 -> group 1
#7 -> group 1
#8 -> group 2
#9 -> group 2
#10-> group 3
...

This example will obviously not work, as group 1 grows too quickly in comparison to groups 2 and 3. Is there a simple division/formula that would achieve the 50/40/20 split?

P.S.: This is not my homework/assignment, but a "real-life" programming problem that I'm facing :)!

Answer 1

One approach is to say that at each stage you should be as close to $\frac 5{11}:\frac 4{11}:\frac 2{11}$ as possible. At the start you are exactly there. Now adding the first person, your choices are $1:0:0, 0:1:0, 0:0:1$ Clearly the first is closest to the ideal, so person $1$ goes in group $1$. Then person $2$ goes in group $2$. For the third, you can have $\frac 23:\frac 13:0$ or $\frac 13:\frac13:\frac13$ Taking the absolute differences from the ideal, the second choice is closer, so number $3$ goes in group $3$. Then clearly $4$ goes in group $1, 5$ goes in $2$, $6$ in $1$, and so on. Because of the symmetry, once you are halfway through you can mirror image. When you have a common divisor, as here, once you get the first tenth of the people you will just repeat. So in your example, the groups are $1,2,3,1,2,1,2,1,3,2,1$

Answer 2

It depends what you want as balanced.

A simple solution would be note that the highest common factor (greatest common divisor if you prefer) of $50$, $40$ and $20$ is $10$, and dividing by $10$ gives $5,4,2$. So $5$ people to Group 1, then $4$ to Group 2 then $2$ to Group 3. Then repeat. Every multiple of $11$, you get the right balance.

If you are aiming for better balance fon non-multiples of $11$ then the pattern $1$, $2$, $3$, $1$, $2$, $1$, $2$, $1$, $3$, $2$, $1$, and then repeated as often as needed, will get you close. This effectively applies the Sainte-Laguë method, dividing the frequency of occurance by odd integers and taking the highest quotients, to minimise chi-square divergence.