CODEWITHSUNDEEP
algorithmoptimizationsplit
Noampz
Noampz

Reputation: 1205

Split M people to N teams with proportion constrains

I have the following problem and I need an algorithm for this. I need to write a program that split M student (in my case they are about 170 student) to N teams (12 teams) with the same number of students in each team as much as possible (in my case 14 or 15 student in a team), and there are 3 constrains. the first constrain is proportions of female/male between the teams should be equal as much as possible. the second constrain is proportions of outstanding/not outstanding students between the teams should be equal as much as possible. the second constrain is proportions of student live in the city/outside the city between the teams should be equal as much as possible.

I don't need to find the optimal split, but split that good enough and I don't have definition what is good enough, maybe the maximum different in the proportion can be an input.

I have all the info I need about the students.

Thanks!!!

Upvotes: 2

Views: 221

Answers (1)

j_random_hacker
j_random_hacker

Reputation: 51226

First, here's a general procedure for splitting a group of M students into N teams as evenly as possible:

  1. Assign RoundDown(M/N) students to each of the N teams, in any manner.
  2. If N is not divisible by M, then N - (M % N) < N "extra" students remain. Assign each of them to a different team.

After doing this, team sizes differ by at most 1 (some teams got no extra students, while some may have gotten exactly 1 extra student). Notice that if we have several separate groups of students then we can perform this procedure several times in succession to build up the N teams, and provided we always add any "extra" students to the smallest teams first, we will always maintain the property that team sizes differ by at most 1.

You have 3 separate criteria, so each student is in one of 2^3 = 8 groups defined by them (e.g. the group of male, non-outstanding, city students). So you can simply perform the above procedure 8 times, once for each group.

This will result in:

  • Team sizes will differ by at most 1.
  • The number of males (or of females, or of outstanding students, etc.) in any two teams will differ by at most 4, since there are 4 groups that include males (males who are/aren't oustanding, and who live/don't live in the city), and we know that for each of these groups, the number of students from that group in a team differs by at most 1.

In practice, it's unlikely that the number of people in any category will differ by as much as 4 between teams. You can mitigate this even further by being careful about which smallest teams get extra students first -- e.g. if you have 3 extra male, non-outstanding, city students left over and there are 7 small teams, you can put them in the 3 teams that have the fewest males (or non-outstanding students, or whichever criterion you want to prioritise). The same applies if there are more extra students in some group than small teams -- if there are 4 small teams and 9 extra students in some group, the first 4 students have to go to the small teams, but the remaining 5 students can go to whichever or the remaining 8 teams gives the best, say, gender balance.

Upvotes: 1

Related Questions