算法：返回一组 32 支球队的所有可能的比赛，这些球队的允许对手较少

Question

我在编写一个算法来返回 32 支球队的所有可能的有效比赛时遇到问题。规则是：

• 赛程表中每对球队仅进行一场比赛。这不需要是循环赛或类似的事情。该算法需要是 32 支球队之间 16 场比赛的所有有效可能性。
• 在家/外出并不重要
• 每支球队只有 14 支其他球队有资格参赛的子集。
• 球队必须有对手。如果某个版本的赛程表最终没有让所有球队都参加比赛，则该赛程表无效且不应退回。

团队的一个例子是

[
  {
    id: "teamId1",
    opponents: ["teamId2", "teamId3", "teamId5", "teamId8", "teamId14", ...etc] // length 14
  },
  {
    id: "teamId2",
    opponents: ["teamId1", "teamId3", "teamId6", "teamId11", "teamId12", ...etc] // length 14
  }
  ...etc
] // length 32

我认为可能有一个递归解决方案对此很优雅，但我真的很难理解它或找到已经存在的适当命名的算法。

我将使用 javascript 来实现这一点，但显然该算法是独立于语言的。但任何专门针对 javascript/使用 javascript 运算符等的示例都会有所帮助。

Answer 1

这可以通过创建一个嵌套循环来完成，该循环获取球队及其对手的每组配对，并将其添加到日程表中（如果该配对尚未包含在日程表中）。这是一个例子：

const teams =  [
  teamId1 = {
    id: "teamId1",
    opponents: ["teamId2", "teamId3", "teamId5", "teamId8", "teamId14"] // length 14
  },
  teamId2 = {
    id: "teamId2",
    opponents: ["teamId1", "teamId3", "teamId6", "teamId11", "teamId12"] // length 14
  }
] // length 32

// Empty aray to store the schedule
const schedule  = [];

// Loop through initial array
teams.forEach(team => {
  // Loop  through subarray of opponents of team
  team.opponents.forEach(opponent => {
    // Make sure that [team, opp] is not already included in schedule
    if (
      !(schedule.includes([team, opponent]))
      && !(schedule.includes([opponent, team]))
    ) {
      // add pairing to schedule
      schedule.push([opponent, team]);
    }
  })
})

console.log(schedule);