循环赛的调度算法？

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

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