algorithm - 将 n 名球员分配到 3 人队以减少重复比赛的次数？

Question

抱歉，标题没有描述性。这不是家庭作业问题——我有一个 friend 让我帮他为他正在举办的 FRC 锦标赛分配队伍。

所以我有 n 个玩家和 x 个游戏。每场比赛有两队，每队三名球员。我想生成一个时间表，尽量减少重复比赛的次数(也就是说，我不希望两支球队互相比赛两次，并且所有事情都是平等的我宁愿每支球队都像可能(所以玩家 A、B 和 C 不会一直在同一个团队中玩))。

我不是在要求一个具体的答案，而是可能会指出我要解决的问题的正式名称是什么？

编辑:

应优先考虑拥有尽可能多的独特(独特)游戏，同时让每个玩家玩几乎相同数量的游戏(游戏最多和最少的玩家之间的差异应该不会更大多于两个，如果可能的话)。

这不是循环赛本身，但如果类似循环赛的锦标赛可以解决这个问题，我想听听如何解决。一个玩家与另一个玩家对战的次数没有限制。

球员可以互换，所以球员 A、B 和 C 的球队等同于球员 A、C 和 B 的球队。

Answer 1

您要查找的一般主题是"combinatorial design" ，这是一个深奥而复杂的数学分支。

完全掌握组合设计肯定会轻松解决您的调度问题。然而这需要几十年的时间，而且该领域的所有专家似乎都在忙着写书。我所能得到的只是可能的游戏数量以 P! 的顺序增加。

幸运的是，一个分支，锦标赛安排，受益于一些非常实际和积极的人的关注，并且一些通用的解决方案被普遍使用。

哪些值得您关注取决于您的锦标赛参数的大小:玩家数量、每轮同时进行的游戏数量以及您有时间进行的轮数。

我的第一个想法是使用 "round-robin" 的修改版调度。如果您的锦标赛超出了循环赛的范围，它可能还有其他更致命的实际困难。

使用循环赛进行团队组合的困难在于，玩家最终总是与玩家列表中距离他们非常近的其他玩家在同一个团队中。所以我修改了我的算法，直到团队组成、比赛组成和必须缺席一轮(轮空)的剩余玩家分布得更均匀。

评论指出了与直接循环法的不同之处，并且我注意到我的最终努力与“冰雹”PRNG 有一些共同的步骤。

parameter PLAYERCNT  // number of players

const TEAMCNT = 2  // number of teams in a game
const SLOTCNT = 3  // number of players on a team

const GAMECNT = trunc(PLAYERCNT / (TEAMCNT * SLOTCNT))  // max num simultaneous games

// the game and team assignment for one round
SEED : array [GAMECNT-1, TEAMCNT-1, SLOTCNT-1] of integer

POOL : array [PLAYERCNT-1] of boolean  // temp to mark selected players

// before generating any rounds:
  BASE = 0
  BUMP = 0
//

// to generate the next round:
  // make all players available for this round
  for PLAYER from 0 to PLAYERCNT-1 { POOL[PLAYER] = false }
  // changing the bump repeatedly breaks up the teams, otherwise players always
  // end up on the same team with someone within SLOTCNT on the player list
  BUMP = BUMP+1  // bump part of hailstone algo
  PLAYER = BASE
  // changing the base distributes the collisions evenly over the list
  // which also distributes the byes (players who have to sit out a round)
  BASE = (BASE + (TEAMCNT * SLOTCNT)) mod PLAYERCNT  // base part of hailstone algo
  // fill in the game and team assignments
  for GAME from 0 to GAMECNT-1 {
    for TEAM from 0 to TEAMCNT-1 {
      for SLOT from 0 to SLOTCNT-1 {
        SEED[GAME, TEAM, SLOT] = PLAYER
        POOL[PLAYER] = true  // mark player as no longer available
        // find next available player while detecting hailstone collisions
        while POOL[PLAYER] {
          PLAYER = (PLAYER + BUMP) mod PLAYERCNT
        }
        //
      }
    }
  }
//