Distributing players to tables
- by IVlad
Consider N = 4k players, k tables and a number of clans such that each member can belong to one clan. A clan can contain at most k players.
We want to organize 3 rounds of a game such that, for each table that seats exactly 4 players, no 2 players sitting there are part of the same clan, and, for the later rounds, no 2 players sitting there have sat at the same table before. All players play all rounds.
How can we do this efficiently if N can be about ~80 large?
I thought of this:
for each table T:
repeat until 4 players have been seated at T:
pick a random player X that is not currently seated anywhere
if X has not sat at the same table as anyone currently at T AND
X is not from the same clan as anyone currently at T
seat X at T
break
I am not sure if this will always finish or if it can get stuck even if there is a valid assignment. Even if this works, is there a better way to do it?
