0

The problem I'm having is that, given a pool of n players in a tournament, I must create teams of two players which must be unique combinations across the tournament's rounds; so that no person has to play on the same team with a person they've played with before.

My conceptualisation of the algorithm is, as in code:

all_players = {
    player: set({player})  # set of prior team mates, include self
    for player in tournament.players
}

team_backlog = []

for round in self.rounds:
    available_team_mates = set(all_players)
    players_in_use = set()
    all_teams = []

    # pair up all possible players
    for player, prior_team_mates in all_players.items():
        if player in players_in_use:
            continue

        for next_team_mate in team_backlog:
            # try match up with any players in the backlog
            if next_team_mate not in prior_team_mates:
                team_backlog.remove(next_team_mate)
                break
        else:
            # otherwise resolve to default round-robin
            compatible_team_mates = available_team_mates - prior_team_mates
            try:
                next_team_mate = compatible_team_mates.pop()
            except KeyError:
                if len(prior_team_mates) < len(all_players):
                    # if there are still candidates for this player to have a team mate
                    team_backlog.append(player)
                continue

        players_in_use |= {next_team_mate, player}
        available_team_mates -= {player, next_team_mate}
        all_players[next_team_mate].add(player)
        prior_team_mates |= {next_team_mate}
        all_teams.append(round.create_team(player, next_team_mate))

That is, to form one team, iterate all players:

  1. Store a "prior team-mate" array for the current player
  2. Check the backlog for a compatible team-mate (not in the prior team-mate array)
    • If it contains a compatible team-mate, form the team with them
      Return to step 1
  3. Otherwise, query the available team-mates for the match (which have not been paired)
    • If there is a match with a team-mate that is not a in the prior team-mate array, take it.
      Return to step 1
  4. Otherwise, as long as we have potential candidates for a pairing in the next round
    Add the player to the backlog, so that we can be prioritised

The primary issue with this algorithm is that it generates an odd amount of teams if/when a suitable pairing could not be found for a certain player, because the player pairings were not evenly distributed in prior matches.
My assumption is that with n players, I can have at most n rounds with optimal scheduling, although I can't explain why.

I've tried researching and tinkering with ChatGPT, but I can't frame the problem well enough. This post seemed related, and furthermore this method, but it doesn't seem to translate into my problem.

uspectaculum
  • 391
  • 2
  • 9

1 Answers1

0
def generate_unique_matchups(self):
    if not self.rounds or not self.players:
        return

    if len(self.players) % 2 == 1:
        self.players.append(Player(**DUMMY_PLAYER))

    unsplit_players = self.rounds[0].free_players.copy()
    random.shuffle(unsplit_players)
    
    ltr_players = unsplit_players[:len(unsplit_players) // 2]
    rtl_players = unsplit_players[len(unsplit_players) // 2:]

    round_information = []

    for round in self.rounds:
        teams = [
            round.create_team(ltr_players[i], rtl_players[i])
            for i in range(0, len(ltr_players))
        ]
        match_ups = [
            round.create_matchup(teams[i], teams[len(teams) // 2 + i])
            for i in range(0, len(teams) // 2)
        ]
        db.session.commit()
        round_information.append({
            "teams": serialize_no_key(teams),
            "matchups": serialize_no_key(match_ups)
        })
        ltr_players.insert(1, rtl_players.pop(0))
        rtl_players.append(ltr_players.pop(-1))
    return round_information

It was far simpler than I initially thought.
Not terribly efficient, but it's conceptually simple.

uspectaculum
  • 391
  • 2
  • 9