Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Return all possible matchups for a set of 32 teams who have a smaller subset of allowable opponents

I’m having a problem writing an algorithm to return all possible valid matchups for a set of 32 teams. The rules are:

  • The schedule is for only one game per pair of teams. This does not need to be a round robin as the teams do not all play each other. The algorithm needs to be all valid possibilities of the 16 games between the 32 teams, but not have any duplicated schedules (with games in different indexes, for example)
  • Home/away does not matter and is not applicable here
  • Each team only has a subset of 14 other teams that they are eligible to play.
  • Teams must have an opponent. If a version of the schedule does not end up with all teams having a match, it is invalid and shouldn’t be returned.

The actual data for the teams and allowable opponents for each team is below:

[
  {
    "id": 1,
    "opponents": [
      8,
      25,
      28,
      2,
      20,
      23,
      19,
      13,
      10,
      4,
      21,
      14,
      32,
      7,
    ],
  },
  {
    "id": 2,
    "opponents": [
      20,
      21,
      32,
      18,
      25,
      28,
      31,
      22,
      23,
      8,
      30,
      11,
      1,
      12,
    ],
  },
  {
    "id": 3,
    "opponents": [
      26,
      6,
      29,
      5,
      24,
      15,
      12,
      23,
      13,
      10,
      9,
      17,
      31,
      22,
    ],
  },
  {
    "id": 4,
    "opponents": [
      14,
      23,
      19,
      8,
      18,
      1,
      31,
      10,
      30,
      11,
      25,
      28,
      26,
      20,
    ],
  },
  {
    "id": 5,
    "opponents": [
      10,
      24,
      9,
      16,
      22,
      6,
      29,
      11,
      26,
      3,
      27,
      7,
      19,
      28,
    ],
  },
  {
    "id": 6,
    "opponents": [
      26,
      3,
      29,
      13,
      10,
      9,
      17,
      14,
      5,
      24,
      15,
      12,
      18,
      27,
    ],
  },
  {
    "id": 7,
    "opponents": [
      16,
      22,
      27,
      5,
      24,
      15,
      12,
      1,
      26,
      13,
      10,
      9,
      17,
      20,
    ],
  },
  {
    "id": 8,
    "opponents": [
      25,
      1,
      28,
      2,
      20,
      23,
      19,
      12,
      9,
      4,
      21,
      14,
      32,
      22,
    ],
  },
  {
    "id": 9,
    "opponents": [
      5,
      10,
      24,
      26,
      3,
      27,
      7,
      31,
      16,
      22,
      6,
      29,
      23,
      8,
    ],
  },
  {
    "id": 10,
    "opponents": [
      5,
      24,
      9,
      26,
      3,
      27,
      7,
      30,
      16,
      22,
      6,
      29,
      4,
      1,
    ],
  },
  {
    "id": 11,
    "opponents": [
      30,
      18,
      31,
      4,
      2,
      20,
      14,
      29,
      21,
      32,
      23,
      19,
      5,
      17,
    ],
  },
  {
    "id": 12,
    "opponents": [
      13,
      17,
      15,
      16,
      22,
      6,
      29,
      2,
      31,
      26,
      3,
      27,
      7,
      8,
    ],
  },
  {
    "id": 13,
    "opponents": [
      17,
      15,
      12,
      26,
      3,
      27,
      7,
      20,
      30,
      16,
      22,
      6,
      29,
      1,
    ],
  },
  {
    "id": 14,
    "opponents": [
      4,
      23,
      19,
      8,
      18,
      1,
      31,
      24,
      30,
      11,
      25,
      28,
      6,
      21,
    ],
  },
  {
    "id": 15,
    "opponents": [
      13,
      17,
      12,
      16,
      22,
      6,
      29,
      21,
      18,
      26,
      3,
      27,
      7,
      25,
    ],
  },
  {
    "id": 16,
    "opponents": [
      22,
      27,
      7,
      13,
      10,
      9,
      17,
      28,
      29,
      5,
      24,
      15,
      12,
      32,
    ],
  },
  {
    "id": 17,
    "opponents": [
      13,
      15,
      12,
      26,
      3,
      27,
      7,
      32,
      11,
      16,
      22,
      6,
      29,
      28,
    ],
  },
  {
    "id": 18,
    "opponents": [
      30,
      11,
      31,
      21,
      32,
      23,
      19,
      6,
      4,
      2,
      20,
      14,
      24,
      15,
    ],
  },
  {
    "id": 19,
    "opponents": [
      4,
      14,
      23,
      30,
      11,
      25,
      28,
      5,
      8,
      18,
      1,
      31,
      29,
      32,
    ],
  },
  {
    "id": 20,
    "opponents": [
      2,
      21,
      32,
      18,
      25,
      28,
      31,
      7,
      4,
      8,
      30,
      11,
      1,
      13,
    ],
  },
  {
    "id": 21,
    "opponents": [
      2,
      20,
      32,
      8,
      30,
      11,
      1,
      27,
      14,
      18,
      25,
      28,
      31,
      15,
    ],
  },
  {
    "id": 22,
    "opponents": [
      16,
      27,
      7,
      13,
      10,
      9,
      17,
      8,
      3,
      5,
      24,
      15,
      12,
      2,
    ],
  },
  {
    "id": 23,
    "opponents": [
      4,
      14,
      19,
      30,
      11,
      25,
      28,
      9,
      8,
      18,
      1,
      31,
      3,
      2,
    ],
  },
  {
    "id": 24,
    "opponents": [
      5,
      10,
      9,
      16,
      22,
      6,
      29,
      18,
      26,
      3,
      27,
      7,
      14,
      25,
    ],
  },
  {
    "id": 25,
    "opponents": [
      8,
      1,
      28,
      4,
      21,
      14,
      32,
      15,
      24,
      2,
      20,
      23,
      19,
      27,
    ],
  },
  {
    "id": 26,
    "opponents": [
      3,
      6,
      29,
      5,
      24,
      15,
      12,
      4,
      13,
      10,
      9,
      17,
      30,
      7,
    ],
  },
  {
    "id": 27,
    "opponents": [
      16,
      22,
      7,
      5,
      24,
      15,
      12,
      25,
      6,
      13,
      10,
      9,
      17,
      21,
    ],
  },
  {
    "id": 28,
    "opponents": [
      8,
      25,
      1,
      4,
      21,
      14,
      32,
      17,
      5,
      2,
      20,
      23,
      19,
      16,
    ],
  },
  {
    "id": 29,
    "opponents": [
      26,
      3,
      6,
      13,
      10,
      9,
      17,
      19,
      5,
      24,
      15,
      12,
      11,
      16,
    ],
  },
  {
    "id": 30,
    "opponents": [
      11,
      18,
      31,
      4,
      2,
      20,
      14,
      26,
      21,
      32,
      23,
      19,
      10,
      13,
    ],
  },
  {
    "id": 31,
    "opponents": [
      30,
      11,
      18,
      21,
      32,
      23,
      19,
      3,
      4,
      2,
      20,
      14,
      9,
      12,
    ],
  },
  {
    "id": 32,
    "opponents": [
      2,
      20,
      21,
      8,
      30,
      11,
      1,
      16,
      19,
      18,
      25,
      28,
      31,
      17,
    ],
  },
]

I’m thinking there probably is a recursive solution that would be elegant for this, but I really am having a problem wrapping my head around it or finding the appropriately named algorithm that already exists.

I will be implementing this using javascript but obviously the algorithm is language independent. But any examples specifically in javascript/using javascript operators etc would help.

Tags:

2

Answers


  1. 0

    This can be accomplished by creating a nested loop that takes every pairing of a team and its opponent and adds it to the schedule if that pairing is not already included on the schedule. Here’s an example:

    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.id, opponent]))
      && !(schedule.includes([opponent, team.id]))
    ) {
      // add pairing to schedule
      schedule.push([team.id, opponent]);
    }
  })
})

console.log(schedule);

    EDIT:

    In response to your comment below, here’s a version of the above code that creates a new permutation for each element in the array:

     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 array to store the schedule
const schedule  = [];

// Loop through initial array
teams.forEach(team => {
  // Array for each permutation
  const permutation = [];

  // Create new array to flatten teamIdn with its opponents
  const allTeams = [team.id, ...team.opponents]
  // Loop through teams array to look for parings
  allTeams.forEach(team1 => {
    // Nested loop to explore every possible pairing
    allTeams.forEach(team2 => {
      // Possible pairings
      const pair1 = [team1, team2];
      const pair2 = [team2, team1];
      // Make sure that pairing or equivalent pairing is not already included in schedule
      if (
        !(permutation.includes(pair1))
        && !(permutation.includes(pair2))
        && schedule.every(i => !(i.includes(pair1)))
        && schedule.every(i => !(i.includes(pair2)))
        && team1 !== team2
      ) {
        // add pairing to schedule
        permutation.push(pair1);
      }
    })
  })

  schedule.push(permutation);
})

console.log(schedule);
    Login or Signup to reply.
  2. 0

    The following code iterates over all possible combinations. There is a slight error, that combinations may be output several times consecutively, so you can either fix the bug, or check consecutively answers for equality.

    The programming concept for this algorithm is called Backtracking, which I apply to a (sorted) list of possible matches.

    export interface Team {
  id: number;
  opponents: number[];
};

export const team_predef: Team[] = []; // Put your team definition here


type Match = [number, number];

class GenerateMatchups {
  // Preparation, filled by constructot
  possibleMatches: Match[];
  teamIds: number[];
  teamIndexInPossibleMatches: number[];

  // State for the matches
  stateMatches: Match[];
  stateTeamIndex: number[];
  stateTeamsWithMatch: Set<number>;
  stateDepth: number;
  /// true => We are currently searching for matches, false we deconstruct to find a new match
  stateInsert: boolean;
  constructor(teams: Team[]) {
    // Team id must be ascending
    this.possibleMatches = [];
    this.teamIds = [];
    this.teamIndexInPossibleMatches = [];
    this.stateTeamsWithMatch = new Set([]);
    this.stateInsert = true; // true ==
    for (const t of teams) {
      this.teamIds.push(t.id);
      // Store where the matches of this team begin
      this.teamIndexInPossibleMatches.push(this.possibleMatches.length);
      // Sort for nicer output
      t.opponents.sort();
      for (const o of t.opponents) {
        // Prevent double inserts [o, t.id] is the same match as [t.id, o]
        if (t.id < o) {
          this.possibleMatches.push([t.id, o]);
        }
      }
    }
    // Final size of possibleMatches at the end
    this.teamIndexInPossibleMatches.push(this.possibleMatches.length);

    this.stateTeamIndex = this.teamIndexInPossibleMatches;
    // TODO Checks for special cases with impossible matches, etc.

  }

  *RecursiveGetNext(matches: Match[] = [], index = 0, usedTeams = new Set<number>([])) {
    if (index < this.teamIds.length) {

      if (matches.length == this.teamIds.length / 2) {
        // Return a copy
        yield [...matches.map(m => [...m])];
      }
      if (usedTeams.has(this.teamIds[index])) {
        for (let x of this.RecursiveGetNext(matches, index + 1, usedTeams)) {
          yield x;
        }
      } else {
        for (let indexMatch = this.teamIndexInPossibleMatches[index];
          indexMatch < this.teamIndexInPossibleMatches[index + 1];
          ++indexMatch) {
          const m = this.possibleMatches[indexMatch];
          if (usedTeams.has(m[0]) || usedTeams.has(m[1])) {
            // Match is not possible, try the next one
            continue;
          }
          matches.push(m);
          usedTeams.add(m[0]);
          usedTeams.add(m[1]);
          for (let x of this.RecursiveGetNext(matches, index + 1, usedTeams)) {
            yield x;
          }
          matches.pop();
          usedTeams.delete(m[0]);
          usedTeams.delete(m[1]);
        }
      }
    }
  }


};


const genMatchups = new GenerateMatchups(team_predef);

let i = 0;
for(const matchup of genMatchups.RecursiveGetNext())
{
  console.log(JSON.stringify(matchup));
  if(++i > 100) // Limit the number of outputs for debugging
  {
    break;
  }
}
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search