Distributing players to tables

algorithm, math, random

Solution

If there are always exactly k players per clan (i.e. 4 clans), you know there should always be 1 person of a clan at a table. In that case, I think it's possible to come up with some predefined rotation scheme where each player, depending on the clan he's from, moves a fixed number of tables further.

I don't think that's possible if the number of clans can be more than 4 (or I don't see it, anyway)

I think your algorithm is pretty good. One way you can prevent it from never terminating (if there are no valid solutions) while still maintaining the randomized behaviour is to not pick a random player infinitely, but to shuffle the list of unseated players once, and process each player from this list in turn:

Edit: I forgot to iterate through the rounds, included this in the algorithm as well.

for each round R in {1, 2, 3}
  for each table T:
    UP = a randomly shuffled list of unseated players
    for each player X from UP
      if there are less than 4 people seated at T AND
         X has not previously sat with any of the players currently at T AND
         X is not from the same clan as anyone currently at T
           seat X at T

    //No more players left to try for this table
    if T has less than 4 people seated
      abort;  //No solution possible (at least, with the decisions taken so far)

  //All tables filled with players, prepare for the next round.
  for each table T:
    for each player X on T:
      Register on X that he has sat with each of the other 3 players at T
    Unseat all players at T

This way, for a single round the algorithm tries all players at most once per table, so that a single run attempts at most 3*T*N times to seat a player before it terminates (either with or without a solution). In other words, a single run should be done pretty quick.

Note that, because it's still randomized it is perfectly acceptable to run this same algorithm multiple times, because it will attempt different combinations of seating every time (making it a so-called Las Vegas algorithm).

Edit 2: Tried and tested this algorithm with 5 clans of 16 players each. Usually, it takes about 400 runs before it finds the first solution, but the total running time is still only about 1 second.

Problem

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?

Original source