安排由两支锦标赛独特配对组成的两支球队进行锦标赛回合

Question

我遇到的问题是，给定锦标赛中的 n 玩家池，我必须创建由两名玩家组成的团队，这在整个锦标赛的轮次中必须是唯一的组合；这样任何人都不必与以前一起玩过的人在同一支球队中比赛。

我对算法的概念化是，如代码所示：

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

即组建一支队伍，迭代所有玩家：

1. 为当前玩家存储一个“之前的队友”数组
2. 检查待办事项中是否有兼容的队友（不在之前的队友数组中）
   • 如果有兼容的队友，请与他们组成团队
     返回步骤 1
3. 否则查询本场比赛可用的队友（尚未配对）
   • 如果与先前队友数组中没有 的队友进行比赛，则接受它。
     返回步骤 1
4. 否则，只要我们有潜在的下一轮配对候选人
   将播放器添加到待办事项列表中，以便我们可以优先考虑

该算法的主要问题是，如果/当无法为某个球员找到合适的配对时，它会生成奇数数量的球队，因为球员配对在之前的比赛中分布不均匀。
我的假设是，对于 n 名玩家，我最多可以进行 n 轮的最佳调度，尽管我无法解释原因。

我尝试过研究和修补 ChatGPT，但我无法很好地描述问题。 这篇文章似乎相关，而且这个方法，但它似乎并没有转化为我的问题。

Answer 1

def generate_unique_matchups(self):
    if not self.rounds:
        return

    players = self.rounds[0].free_players.copy()
    if len(players) % 2 == 1:
        self.players.append(Player(first_name="n/a"))
    random.shuffle(players)

    fixed_rotate_list = lambda l: l.insert(1, l.pop(-1))

    for round in self.rounds:
        teams = [
            round.create_team(players[i], players[len(players) // 2 + i])
            for i in range(0, len(players) // 2)
        ]
        fixed_rotate_list(players)

这比我最初想象的要简单得多