I have a game which can be played by groups of users competing with each other. The number of such groups is very small, under 10. The number of players is thousands.
When a user buys a ticket, a group is assigned to him. Currently, assigning a group to a player is randomly done, but this can lead to cases with a lot of players in a group and very few in others.
The problem I'm stuck with is how to assign group numbers such that the groups have comparable sizes.
Keep a HashMap<Integer, List<Group>>, keyed on the size of the group in question. Everyone starts off in the zero-member bracket. Pop a group off the top of the smallest nonempty size bracket you have, add the new member to it, and push it on to the next largest size.
You get O(n) to create it, O(1) to push and pop off a group, and you can get O(1) to find the smallest group if you keep it cached between calls and just find the next one whenever your current one runs out.
Some subset of the groups will currently have minimum size. (This could be the entire set of groups, if all of them have the same size.) From among this set of minimum-size groups, pick one at random, and add the new player to it.
If you follow this strategy from the start, then no two groups will ever differ in size by more than 1. This is the smallest achievable worst-case size difference.
How about something like this:
GroupManager::AssignGroup(Player player)
{
groupAssignments[groupIndex].add(player);
groupIndex++;
if ( groupIndex == GROUP_MAX )
groupIndex == 0;
}
