函数用于在锦标赛中设置会议。

Question

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

我正在尝试编写一个函数，该函数将返回一个数组，其中包含一组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的每支球队只玩一次。你有什么办法吗？

Answer 1

在你的问题中，这类比赛被称为“循环赛”--它是一种众所周知的比赛形式/类型，因此已经有一些算法可以解决你的问题。

我只是把其中一种调度算法(圆圈法)“翻译”成JS。

对圆法的粗略解释是：

首先，将团队配对如下：

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

1保持固定，每个其他团队顺时针旋转一个位置。因此，在第2轮中，配对如下所示：

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

你这样做，直到你结束你的起点，并在那时，你将有配对/会议为每一轮。

有关进一步的详细信息(以及证明该算法工作的理由，请参见：算法 )

下面是我编写的代码，用于执行我前面解释过的算法。

*如果你通过奇数队，这个函数只会增加1支球队(这将被视为不打本轮的对手)--例如，如果你有5支球队，就会有一支第6队(无论谁打第6队，就是不打那一轮)。

​

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

​

Answer 2

在进入解决方案之前，有几个观察：

• 由于要求每个团队每次会议只能进行一次比赛，对于n团队来说，至少需要召开一次n + n % 2 - 1会议。也就是说:对于偶数的团队，会有n - 1会议，而对于奇数的团队，将有n会议(由于事实是，一个团队将是一个奇怪的人，并且将无法比赛)。
• 下面的解决方案提供了一种回溯方法。回溯本质上是一种递归的蛮力算法，它递增地构建一个解决方案，如果该解决方案在后续步骤中不成功，则返回它的步骤。在组合学中可能有更有效的算法，如果其他用户发布，我很乐意在这里阅读它们。
• 我保持了算法的简单性，但是还有一些额外的调整和启发可以用来极大地提高性能。就像现在一样，它会在我中等规格的笔记本电脑上为多达16个团队带来几乎即时的结果。在那之后，事情就慢了很多。我在这个答案的末尾指出了一些可能改进的解释，但在一天结束时，这仍然是一个具有指数(或至少是阶乘)时间复杂性的算法。

以下是解决办法：

​

const schedule = (n) => {
    const teams = [...Array(n).keys()];
    const games = teams.flatMap(
        (t1, i) => teams.slice(i + 1).map((t2) => [t1, t2])
    );
    const meetings = Array.from(Array(n + n % 2 - 1), () => []);

    if (solve(games, meetings, 0, 0)) {
        return meetings;
    }

    throw new Error('No solution found');
}

const solve = (games, meetings, gi, mi) => {
    if (gi === games.length) {
        return true;
    }

    if (satisfies(games[gi], meetings[mi])) {
        meetings[mi].push(games[gi]);

        for (let i = 0; i < meetings.length; i++) {
            if (solve(games, meetings, gi + 1, i)) {
                return true;
            }
        }

        meetings[mi].pop();
    }

    return false;
}

const satisfies = (game, meeting) => {
    const [t1, t2] = game;
    const played = new Set(meeting.flat());

    return !played.has(t1) && !played.has(t2);
}

console.log(schedule(4));

​

对于4个小组，这将产生以下结果：

[
  [ [ 0, 1 ], [ 2, 3 ] ],
  [ [ 0, 2 ], [ 1, 3 ] ],
  [ [ 0, 3 ], [ 1, 2 ] ]
]

对于8支球队来说，情况如下：

[
  [ [ 0, 1 ], [ 2, 3 ], [ 4, 5 ], [ 6, 7 ] ],
  [ [ 0, 2 ], [ 1, 3 ], [ 4, 6 ], [ 5, 7 ] ],
  [ [ 0, 3 ], [ 1, 2 ], [ 4, 7 ], [ 5, 6 ] ],
  [ [ 0, 4 ], [ 1, 5 ], [ 2, 6 ], [ 3, 7 ] ],
  [ [ 0, 5 ], [ 1, 4 ], [ 2, 7 ], [ 3, 6 ] ],
  [ [ 0, 6 ], [ 1, 7 ], [ 2, 4 ], [ 3, 5 ] ],
  [ [ 0, 7 ], [ 1, 6 ], [ 2, 5 ], [ 3, 4 ] ]
]

实施本身包括三个职能：

1. satisfies(game, meeting) 该函数检查是否仍然可以将特定的游戏(例如，团队1和团队2)添加到会议中。这完全取决于其中一支或两支球队是否已经在那次会议上安排了比赛。这里有几个简单的改进：

- The maximum number of games per meeting is the quotient of the total number of games divided by the total number of meetings. When deciding whether a game can be added to a meeting, you can skip meetings that are already full.
- The creation of the lookup `Set` to determine which teams are already playing in a meeting has a relatively high time-complexity. You can sacrifice some space-complexity instead, and just keep a running track of those sets without recreating them on every invocation.

1. solve(games, meetings, gi, mi) 这个函数递归地调用自己，试图将游戏分配给会议。

- This function first checks the game index (`gi`) to see whether there are still games to process; if not, the solution is complete.
- Then, if the conditions described in the previous function are satisfied, it will assign the current game (at the specified index `gi`) to the meeting at index `mi`.
- Subsequently, it will call itself recursively to find a meeting to which the _next_ game can be added. If it fails to find such a meeting, it will _backtrack_ by removing the current game from its allocated meeting. Here, it's important to understand that, due to the nature of the algorithm, it might repeatedly come to a near-solution and then have to backtrack halfway back up the tree to start evaluating the next candidate solution.

1. schedule(n) 这是一个驱动函数，它试图为n团队创建一个名册。它准备teams、games和meetings数组，然后调用solve()函数将第一个游戏分配给第一次会议，这将启动调度过程的其余部分。