Javascript 在锦标赛中设置会议的功能

发布于11月12日

我有一个返回数组的函数getMeetingsPossibilities().例如，我有4个团队，它将返回['0-1', '0-2', '0-3', '1-2', '1-3', '2-3'].

我正在try 编写一个函数，该函数将返回一个数组，其中包含n次所需的一组会议.

例如，getSetsOfMeetings(3)(包含4个团队)将返回类似[['0-1','2-3'], ['0-2','1-3'], ['0-3','1-2']] 的结果

我想不出该怎么做，我试了很多次都是徒劳的.

我在想这样的事情:

let meetingsPossibilities = getMeetingsPossibilities(participantsList.length);
//return for 4 teams : ['0-1', '0-2', '0-3', '1-2', '1-3', '2-3']

//Taking out a meeting from meetingPossibilities each time it is used
let oneSetOfMeeting = [];
oneSetOfMeeting.push(meetingPossibilities.splice(randomNumber, 1);

但我无法理解每oneSetOfMeeting 支球队只打一场比赛的逻辑. 你有什么办法做这件事吗？

推荐答案

你问题中的那种锦标赛被称为"循环赛"--这是一种非常著名的锦标赛形式/类型，因此已经有算法试图解决你的问题.

我只是采用了其中一种调度算法(循环法)，并将其"翻译"成JS.

圆法的粗略解释是:

首先将团队配对，如下所示:

1   2    3    4  ...  n/2
n  n-1  n-2  n-3 ... n/2+1

1人保持不变，其他队顺时针旋转一个位置.因此，在第二轮中，配对如下所示:

 1    n    2    3  ... n/2-1
n-1  n-2  n-3  n-4 ...  n/2

你这样做，直到你结束你开始的地方，在这一点上，你将有每一轮的配对/会议.

有关更多详细信息(以及此算法有效的证据/原因，请参阅:https://en.wikipedia.org/wiki/Round-robin_tournament#Scheduling_algorithm

下面是我编写的代码，用来做我上面解释的算法所做的事情.

*如果你通过了奇数支球队，该函数将只增加1支球队(将被视为对手不打这一轮)-例如，如果你有5支球队，时间表中将有第六支球队(无论谁打第六支球队，都不会打那一轮)

function getSchedule(numberOfTeams) {
  if (numberOfTeams % 2 === 1)
    numberOfTeams++;
  const Array1 = [...new Array(numberOfTeams / 2).keys()].map((x) => x + 1);
  const Array2 = [];
  for (let i = numberOfTeams; i > numberOfTeams / 2; i--) {
    Array2.push(i);
  }
  const schedule = [];
  for (let i = 0; i < numberOfTeams - 1; i++) {
  
    // the next two lines can be used interchangeably 
    //(first line has meetings as "1-2, 3-4" - second line has them as [1, 2], [3, 4])
    // just use whatever line serves your purpose best (unit test only works with 2nd line)
    schedule.push(Array1.map((team1, index) => `${team1}-${Array2[index]}`))
    // schedule.push(Array1.map((team1, index) => [team1, Array2[index]]));
    
    Array2.push(Array1.pop() || 0); // the short circuit is only here because I use typescript
    Array1.splice(1, 0, Array2.splice(0, 1)[0]);
  }
  return schedule;
}

console.log(getSchedule(8))
console.log(getSchedule(5))
//yes the 99 is just to show that the function is not that demanding/timecomplex (and could be used to compute large tournaments)
console.log(getSchedule(99))

由于您得到的重用(特别是对于较大数量的团队)手动判断可能的错误是相当困难/乏味的，所以我编写了一个测试来为我做这件事(因为我想判断我编写的内容是否真的产生了想要的输出).既然是我写的，为什么不和你一起分享呢？下面是函数以及附加的函数单元测试

function getSchedule(numberOfTeams) {
  if (numberOfTeams % 2 === 1)
    numberOfTeams++;
  const Array1 = [...new Array(numberOfTeams / 2).keys()].map((x) => x + 1);
  const Array2 = [];
  for (let i = numberOfTeams; i > numberOfTeams / 2; i--) {
    Array2.push(i);
  }
  const schedule = [];
  for (let i = 0; i < numberOfTeams - 1; i++) {

    // the next two lines can be used interchangeably 
    //(first line has meetings as "1-2, 3-4" - second line has them as [1, 2], [3, 4])
    // just use whatever line serves your purpose best (unit test only works with 2nd line)
    // schedule.push(Array1.map((team1, index) => `${team1}-${Array2[index]}`))
    schedule.push(Array1.map((team1, index) => [team1, Array2[index]]));

    Array2.push(Array1.pop() || 0); // the short circuit is only here because I use typescript
    Array1.splice(1, 0, Array2.splice(0, 1)[0]);
  }
  return schedule;
}


//everything below this line is just for testing if we get the desired result (because I can't be bothered to check manually)

function testGetSchedule(schedule) {
  //tests if every round each team only plays once
  if (
    schedule.map(round => new Set(round.flat()).size === round.flat().length).every((x) => x)
  )
    console.log("every team plays only once per round");

  //sorts each meeting (yes array.sort() does not sort numbers as you would expect, but it sorts consistent so it's sufficient)
  const allMeetings = schedule.flat(1);
  allMeetings.forEach((meeting) => meeting.sort());

  //tests if there are any duplicate meetings
  if (new Set(allMeetings.map((meeting) => `${meeting[0]}-${meeting[1]}`)).size === allMeetings.length)
    console.log("no duplicate meetings");
}

testGetSchedule(getSchedule(8))
testGetSchedule(getSchedule(5))
testGetSchedule(getSchedule(99))