将玩家分配到桌子上

Question

考虑有N=4k个玩家，k张桌子和若干个团队，每个成员只能属于一个团队。一个团队最多可以包含k个玩家。

我们想要组织3轮游戏，使得对于每张恰好容纳4个玩家的桌子，没有两个坐在那里的玩家属于同一个团队，并且对于后面的回合，没有两个坐在那里的玩家之前曾经坐过同一张桌子。所有玩家都会参加所有回合。

如果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

我不确定这个程序是否总是能够完成，即使有有效的赋值也可能会卡住。即使这个方法可行，是否还有更好的方法？

- IVlad

---

“N = 4k” 是指 “N = 4000” 吗？还是指表的数量是“k”的4倍？ - Shmiddty

@Shmiddty - k是一个变量，它是桌子数量的4倍。 - IVlad

这对于每个氏族的玩家数量也是适用的吗？ - Shmiddty

我假设每张桌子可以坐4个玩家？ - Shmiddty

后续回合会发生什么？所有玩家都参与吗？谁赢谁输有关系吗？还是只是桌子的重新组织？ - Bitwise

Answer 1

如果每个公会始终恰好有k个玩家（即4个公会），则您知道每张桌子上应该总有一个公会的人。在这种情况下，我认为可以制定一些预定义的轮换方案，其中每个玩家根据他来自的公会移动固定数量的桌子。

如果公会数量可以超过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

这种算法的每一轮最多只尝试一次每个桌子上的所有玩家，因此在终止前（有或没有解决方案），单次运行最多尝试3*T*N次来安排一个玩家的位置。换句话说，单次运行应该很快完成。

请注意，由于它仍然是随机的，因此多次运行同一算法是完全可以接受的，因为它每次都会尝试不同的座位组合（这使其成为所谓的拉斯维加斯算法）。 编辑2:使用这个算法测试了5个由16名玩家组成的团队。通常，需要大约400次运行才能找到第一个解决方案，但总运行时间仍然只有约1秒钟。

- Leon Bouquiet

---

具有正好k个玩家的四个氏族的要求可以稍微放宽一下。如果可能将氏族组合成每个都有k个玩家的4个“超级氏族”，则您的旋转方法仍将起作用，因为这样做保留了以下事实：如果两个玩家属于不同的超级氏族，则它们必须属于不同的氏族。 - j_random_hacker

Answer 2

它卡住了

在座位级别卡住了

我不确定这是否总是会完成，或者即使有有效的分配也可能会卡住。

它可能会卡住。假设 k = 4 张桌子，N = 16 名玩家，4 个氏族，每个氏族有 4 人。让 A1 到 A4 成为氏族 A 的玩家，其他氏族也同理。然后以下是一个手工制作的情况示例，可能会出现在您的算法中：

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 !!!

卡在回合层面了吗？

一个有趣的问题仍然存在：如果所有三个回合都有有效的分配，那么你能否找到两个回合的有效分配，以排除第三个回合的所有有效分配？如果是这种情况，你可能会在回合层面上卡住，因此在进行一些回溯算法时，你可能需要有时撤销完整的回合，以获得有效的解决方案。我没有例子表明这种情况确实发生过，也没有强烈的直觉。

更好的方法

有没有更好的方法来做这件事

我想，通过足够的努力，人们可以将其压缩到某些标准图算法的框架中。最有可能的是，该图问题将是NP难的，因此对于它也不会有多项式时间算法可用。

Donald Knuth写了一篇关于跳跃链接及其在解决精确覆盖问题中的应用的好文章。在最坏情况下，它仍然使用回溯和指数时间，但它使数据结构小，以便在搜索树的大部分工作都完成的那些部分加速搜索。也许这些想法中的一些可以应用于您的情况。只是猜测，尚未考虑特定的实现。

另一个想法：也许您可以采用“增广路径”的概念，就像在计算匹配时使用的那样。这个想法大致如下：如果没有可用的未入座人员，请从其他玩家中选择任意一个人。如果该人与当前桌子兼容，则将其移动到该桌子上。通过这样做，另一张桌子就会少一个玩家，并且您可以尝试使用一些未入座的玩家来填补这个空缺。如果这样做不起作用，您可以再次重新安排一个已经入座的玩家。您可能不应该立即开始移动玩家。相反，您应该首先尝试找到一个完整的增广路径，从空座位开始，到达未入座的人员结束。只有在验证存在这样一个链之后，您才可以按照它移动人员。

- MvG