将玩家分配到桌子上

考虑N = 4k玩家，k桌子和许多氏族，以便每个成员可以属于一个氏族。一个氏族最多可以包含k玩家。

我们想要组织 3 轮游戏，这样，对于每张正好容纳 4 名玩家的桌子，坐在那里的 2 名玩家不会属于同一部落，并且在后面的几轮中，坐在那里的 2 名玩家不会坐在同一位置之前的表。所有玩家都参加所有回合。

如果N可以是关于~80 large?

我想到了这一点：

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

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

如果每个部落总是有 k 名玩家（即 4 个部落），那么您就知道桌子上应该始终有一个部落的 1 个人。在这种情况下，我认为可以提出一些预定义的轮换方案，其中每个玩家根据他所在的部落，进一步移动固定数量的桌子。

我认为如果部落数量超过 4 个，这是不可能的（或者无论如何我都看不到）

我觉得你的算法非常好。可以防止它永远终止（如果没有有效的解决方案）同时仍然保持随机行为的一种方法是不要无限地选择随机玩家，而是对未就座的玩家列表进行一次洗牌，并处理此列表中的每个玩家转动：

Edit：我忘了迭代各轮，也将其包含在算法中。

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

这样，对于单轮，算法在每个桌子上最多尝试一次所有玩家，因此单次运行在终止之前最多尝试 3*T*N 次让玩家入座（无论有或没有解决方案）。换句话说，单次运行应该很快就能完成。

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

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