循环赛的安排算法？

Question

我最近做了一些研究，并与唐纳德·高德纳 (Donald Knuth) 会面。但我没有找到解决我的问题的正确算法。

问题 我们有一个由 n 名玩家组成的联盟。每周他们都会有一场比赛。在 n-1 周内，每个团队都互相对抗。每天有 n/2 场比赛。但一支球队一周只能比赛一次。如果我们生成一个 (n/k) 组合，我们会得到所有组合...（假设 k = 2），但我需要按正确的顺序排列它们。

我的第一个建议是......不是最好的。我只是做了一个数组，然后让计算机尝试是否找到了正确的方法。如果没有，回到开始，打乱数组并再次执行，好吧，我用 PHP 编写了它（n = 8）并且结果有效，但是需要很多时间，对于 n = 16 它给了我一个超时以及。

所以我想我们是否可以找到一种算法，或者有人知道一本涵盖这个问题的书。

这是我的代码： http://pastebin.com/Rfm4TquY

Answer 1

经典算法的工作原理如下：

将团队编号为 1..n。 （这里我取n=8。）

将所有球队写成两行。

1 2 3 4
8 7 6 5

这些列显示了该轮比赛的球队（1 对 8、2 对 7，...）。

现在，保持 1 队固定，但轮换所有其他球队。在第 2 周，您得到

1 8 2 3
7 6 5 4

，在第 3 周，您得到

1 7 8 2
6 5 4 3

这将持续到第 n-1 周，在这种情况下，

1 3 4 5
2 8 7 6

如果 n 是奇数，则执行相同的操作，但添加一个虚拟团队。无论谁与虚拟球队比赛，那周都会再见。

Answer 2

下面是它的 JavaScript 代码。

function makeRoundRobinPairings(players) {
  if (players.length % 2 == 1) {
    players.push(null);
  }

  const playerCount = players.length;
  const rounds = playerCount - 1;
  const half = playerCount / 2;

  const tournamentPairings = [];

  const playerIndexes = players.map((_, i) => i).slice(1);

  for (let round = 0; round < rounds; round++) {
    const roundPairings = [];

    const newPlayerIndexes = [0].concat(playerIndexes);

    const firstHalf = newPlayerIndexes.slice(0, half);
    const secondHalf = newPlayerIndexes.slice(half, playerCount).reverse();

    for (let i = 0; i < firstHalf.length; i++) {
      roundPairings.push({
        white: players[firstHalf[i]],
        black: players[secondHalf[i]],
      });
    }

    // rotating the array
    playerIndexes.push(playerIndexes.shift());
    tournamentPairings.push(roundPairings);
  }

  return tournamentPairings;
}

更新：
修复了评论中报告的错误

Answer 3

我制作了这段代码，关于 冈崎 解释

const roundRobin = (participants) => {
  const tournament = [];

  const half = Math.ceil(participants.length / 2);
  const groupA = participants.slice(0, half);
  const groupB = participants.slice(half, participants.length);
  groupB.reverse();

  tournament.push(getRound(groupA, groupB));


  for(let i=1; i < participants.length - 1; i ++) {
    groupA.splice(1, 0, groupB.shift());
    groupB.push(groupA.pop())
    tournament.push(getRound(groupA, groupB));
  }

  console.log(tournament)
  console.log("Number of Rounds:", tournament.length)
  return tournament;
}

const getRound = (groupA, groupB) => {
  const total = [];
  groupA.forEach((p, i) => {
    total.push([groupA[i], groupB[i]]);
  });
  return total;
}

roundRobin([1,2,3,4,5,6,7])

PS：我举了一个奇数的例子，所以有一个队伍不是每轮都打，与undefined决斗，你可以按照你想要的方式定制它

Answer 4

我使用可重用函数为此创建了一个更新的解决方案（受到 varun 的启发）：

const testData = [
  "Red",
  "Orange",
  "Yellow",
  "Green",
  "Blue",
  "Indigo",
  "Violet",
];

const matchParticipants = (participants) => {
  const p = Array.from(participants);
  if (p % 2 == 1) {
    p.push(null);
  }
  const pairings = [];
  while (p.length != 0) {
    participantA = p.shift();
    participantB = p.pop();
    if (participantA != undefined && participantB != undefined) {
      pairings.push([participantA, participantB]);
    }
  }
  return pairings;
};

const rotateArray = (array) => {
  const p = Array.from(array);
  const firstElement = p.shift();
  const lastElement = p.pop();
  return [firstElement, lastElement, ...p];
};

const generateTournament = (participants) => {
  const tournamentRounds = [];
  const rounds = Math.ceil(participants.length / 2);
  let p = Array.from(participants);
  for (let i = 0; i < rounds; i++) {
    tournamentRounds.push(matchParticipants(p));
    p = rotateArray(p);
  }
  return tournamentRounds;
};

console.log(generateTournament(testData));

Answer 5

这是Python中的代码，供感兴趣的人参考：

def makePairing(inputList):
    if len(inputList) % 2 == 1:
        inputList.append("No Opponent")
    
    pairings = list()
    
    for round in range(len(inputList) - 1):
        round_pairings = list()
        first_half = inputList[:int(len(inputList)/2)]
        second_half = list(reversed(inputList[int(len(inputList)/2):]))

        for element in range(len(first_half)):
            round_pairings.append((first_half[element], second_half[element]))
            
        pairings.append(round_pairings)
        inputList = inputList[0:1] + inputList[2:] + inputList[1:2]
    
    return pairings