Distributing players to tables

问题:

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?

回答1:

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.

回答2:

It gets stuck

Stuck at the seat level

I am not sure if this will always finish or if it can get stuck even if there is a valid assignment.

It may get stuck. Assume k = 4 tables, N = 16 players, 4 clans, 4 people in each clan. Let A1 thrugh A4 be the players in clan A and similarly for the other clans. Then the following is an example of a hand-crafted situation which could potentially arise from your algorithm:

Round 1:
 Table 1: A1, B1, C1, D1
 Table 2: A2, B2, C2, D2
 Table 3: A3, B3, C3, D3
 Table 4: A4, B4, C4, D4

Round 2:
 Table 1: A1, B2, C3, D4
 Table 2: A2, B3, C1 !!!

Stuck at the round level?

An interesting question that still remains is the following: if a valid assignment for all three rounds is possible, can you find valid assignments for two rounds that preclude all valid assignments for the third round? If this were the case, you could get stuck at the round level, so when doing some backtracking algorithm, you might have to sometimes undo complete rounds in order to obtain a valid solution. I have no example where this does happen, and no strong gut feeling either way.

Better ways

is there a better way to do it

I guess that with enough effort, one could squeeze this into the framework of some standard graph algorithm. Most likely, that graph problem would be NP hard, so there won't be polynomial time algorithms available for that either.

Donald Knuth wrote a nice paper about dancing links and their application to solving the exact cover problem. It still uses back-tracking and exponential time in the worst case, but it keeps data structures small for those parts of the search tree where most work is done, thus speeding up the search. Maybe some of these ideas can be applied to your situation as well. Just guessing, though, don't have a particular implementation in mind yet.

Another idea: perhaps you can adopt the concept of augmenting paths, as it is used when computing matchings. The idea goes something like this: if there is no unseated person available, pick an arbitrary person from some other player. If that person is compatible with the current table, move it to that table. By doing so, that other table would be short one player, and you could try to fill that gap using some unseated player. If that doesn't work, you re-seat an existing player again. You probably shouldn't start moving players right away. Instead, you should first try to find a full augmenting path, starting at a vacant seat and ending at an unseated person. Only after you have verified that such a chain exists, you can start moving people according to it.