循环赛程算法是什么？

Question

我最近研究了一些东西并与Donald Knuth见面了。但是我没有找到解决我的问题的正确算法。

问题 我们有一个由n个选手组成的联赛。每周他们会和另一个选手比赛。在n-1周内，每个团队都会对抗其他团队。每天有n/2场比赛。但是一支队伍一周只能比一次。如果我们生成一个(n/k)组合，我们就可以得到所有的组合...（假设k=2），但我需要按正确的顺序排列它们。

我的第一个建议不是最好的。我只是创建了一个数组，然后让计算机尝试找到正确的方式。如果找不到，则返回起点，洗牌数组并重新开始。嗯，我用PHP编写了它（n=8），输出结果没问题，但是需要很长时间，对于n=16，我还遇到了超时的情况。

因此，我想知道是否有算法，或者是否有任何涵盖这个问题的书籍。

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

- Philipp Spiess

---

循环赛是一种比赛形式，其中每个参赛者都必须与其他参赛者比赛一次。为了避免在任何一轮中有参赛者空闲或重复比赛的情况发生，可以使用循环赛编排算法来确定每个参赛者应该在哪些轮次中进行比赛。在这种算法中，参赛者被分成两组，并且每个参赛者都会交替与来自另一个组的参赛者进行比赛。这种方法可以以一种公平和可预测的方式来安排比赛，适用于各种竞技和游戏比赛。 - Gareth Rees

我在这里添加了这条评论，因为这个话题似乎是一个将一些好奇的人引向CodeReview上相关话题的合适场所。 - Redu

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

在第三周，您将获得

1 7 8 2
6 5 4 3

这将持续到第 n-1 周，例如：

1 3 4 5
2 8 7 6

如果n是奇数，执行相同的操作但添加一个虚拟队伍。与虚拟队伍匹配的人在那一周得到一个bye。

- Chris Okasaki

---

为什么我们只固定一个并旋转其他的呢？为什么不能全部旋转？ - sam202252012

试试吧！从上面的第一个配置开始，轮流旋转每个人。选择你最喜欢的数字并记录与之匹配的人。在完成整个周期之前，你会注意到一个问题。 - Chris Okasaki

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;
}

更新： 修正了评论中报告的一个错误

- varun

---

看到@varun的代码有一个bug。 使用：['a','b','c','d'] [第一轮] 0: {p1: "a", p2: "c"} 1: {p1: "a", p2: "b"} [第二轮] 0: {p1: "a", p2: "d"} 1: {p1: "b", p2: "c"} [第三轮] 0: {p1: "a", p2: "a"} 1: {p1: "c", p2: "d"} - There

关于@varun代码中的错误，这是修复方法：将“let playerIndexes = players.slice(1).map((, i) => i);”更改为“let playerIndexes = p.map((, i) => i); playerIndexes.shift();”。 - There

谢谢你救了我的命，伙计！你的算法太棒了！我也尝试过https://dev59.com/vGw15IYBdhLWcg3wYasx，但那段代码完全错误！ - Emu

非常感谢！这帮助我解决了长期以来的困境，哈哈。谢谢！ - Nirvan Nagar

Answer 3

我编写了这段代码，与Okasaki的解释相关。

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])

附言：我提供了一个奇数数量的例子，这样就会有一支球队在某些轮次没有比赛，与undefined对决，您可以按照自己的方式进行自定义

- Dr.G

Answer 4

对于那些感兴趣的人，这是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

- Arcyno

Answer 5

我使用可重用函数（受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));

- Joe Sadoski