algorithm - 分配玩家到 table

Question

考虑 N = 4k 玩家、k table 和多个氏族，这样每个成员都可以属于一个氏族。一个氏族最多可以包含 k 个玩家。

我们想要组织一场比赛的 3 轮比赛，使得每张 table 恰好有 4 名玩家入座，没有 2 名坐在那儿的玩家属于同一战队，并且在后面的几轮比赛中，没有 2 名坐在那儿的玩家已经坐下之前同 table 。所有玩家玩所有回合。

如果 N 可以大约 ~80 大，我们如何才能有效地做到这一点？

我想到了这个:

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

我不确定这是否总是会完成，或者即使有有效的分配也会卡住。即使这行得通，还有更好的方法吗？

Answer 1

如果每个部落总是恰好有 k 个玩家(即 4 个部落)，您知道一张 table 上应该总是有 1 个部落成员。在那种情况下，我认为有可能提出一些预定义的轮换方案，其中每个玩家根据他来自的氏族，进一步移动固定数量的 table 。

如果氏族的数量超过 4 个，我认为这是不可能的(或者我没看到，无论如何)

我觉得你的算法很不错。您可以防止它永不终止(如果没有有效的解决方案)同时仍然保持随机行为的一种方法是不要无限地选择随机玩家，而是将未就座的玩家列表洗牌一次，然后处理此列表中的每个玩家转:

编辑:我忘了遍历轮次，也将其包含在算法中。

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

这样，对于一个回合，算法最多尝试每张 table 一次所有玩家，因此单次运行最多尝试 3*T*N 次让玩家入座，然后终止(有或没有解决方案) .换句话说，单次运行应该很快完成。

请注意，因为它仍然是随机的，所以多次运行相同的算法是完全可以接受的，因为它每次都会尝试不同的座位组合(使其成为所谓的拉斯维加斯算法)。

编辑 2:在 5 个部落(每个部落 16 名玩家)中尝试并测试了该算法。通常，它需要大约 400 次运行才能找到第一个解，但总运行时间仍然只有 1 秒左右。