如何用Python实现无重复搭档的羽毛球双打循环赛配对器？

问题背景 #

需要实现一个羽毛球双打赛事配对器，满足以下要求：

• 选手数量为偶数，每位选手每轮必须参赛
• 每位选手不会与同一搭档配对超过一次
• 原实现通过NetworkX图记录已搭档关系，但后续轮次会出现无法凑齐有效队伍的情况——未搭档的选手已被其他队伍选中，导致部分选手落单。

解决方案 #

核心思路是将问题转化为无向图的完美匹配问题：

• 用图节点表示选手，已搭档过的选手间连权重为0的边，未搭档的连权重为1的边
• 使用NetworkX的nx.max_weight_matching算法寻找完美匹配，该算法会优先选择权重高的边（即未搭档的选手组合），确保覆盖所有选手且无重复搭档。

修改后的完整代码 #

import networkx as nx

class Player:
    def __init__(self, name: str):
        self.name = name
        self.previous_partners = set()
        self.score = 0.0

    def __str__(self):
        return self.name

    def __hash__(self):
        # 必须实现hash，否则无法作为NetworkX节点
        return hash(self.name)

class Team:
    def __init__(self, players: list):
        if len(players) != 2:
            raise ValueError('一支队伍必须恰好有两名选手')
        self.players = players

    def __str__(self):
        return ' / '.join([str(player) for player in self.players])

class RoundRobinMatcher:
    @staticmethod
    def _create_weighted_graph(players: list[Player]) -> nx.Graph:
        graph = nx.Graph()
        for player in players:
            graph.add_node(player)
        
        # 为所有未搭档的选手对添加权重1的边，已搭档的添加权重0的边
        for i in range(len(players)):
            p1 = players[i]
            for j in range(i+1, len(players)):
                p2 = players[j]
                weight = 0 if p2 in p1.previous_partners else 1
                graph.add_edge(p1, p2, weight=weight)
        return graph

    def match(self, players: list[Player]) -> list[Team]:
        if len(players) % 2 != 0:
            raise ValueError('选手数量必须为偶数')
        
        graph = self._create_weighted_graph(players)
        # 寻找最大权重匹配，设置maxcardinality=True确保覆盖所有节点（完美匹配）
        matching = nx.max_weight_matching(graph, maxcardinality=True)
        
        # 转换为Team对象，同时去重（因为匹配是双向的，比如(p1,p2)和(p2,p1)是同一个）
        used_players = set()
        teams = []
        for p1, p2 in matching:
            if p1 not in used_players and p2 not in used_players:
                teams.append(Team([p1, p2]))
                used_players.add(p1)
                used_players.add(p2)
                # 更新选手的搭档记录
                p1.previous_partners.add(p2)
                p2.previous_partners.add(p1)
        
        return teams

if __name__ == '__main__':
    players = [Player('a'), Player('b'), Player('c'), Player('d'), 
               Player('e'), Player('f'), Player('g'), Player('h')]
    matcher = RoundRobinMatcher()
    
    # 模拟5轮赛事
    for round_num in range(1, 6):
        print(f"=== 第{round_num}轮配对 ===")
        teams = matcher.match(players)
        for team in teams:
            print(team)
        print()

关键改动说明 #

1. 添加__hash__方法：Player类必须实现hash，才能作为NetworkX图的节点使用
2. 加权图构建：区分已搭档（权重0）和未搭档（权重1）的选手对，引导算法优先选择新搭档
3. 完美匹配算法：使用nx.max_weight_matching并设置maxcardinality=True，确保所有选手都能配对
4. 搭档记录更新：每轮配对后立即更新选手的previous_partners集合，避免后续轮次重复配对
5. 去重处理：匹配结果会包含双向边，需要去重后生成唯一的Team对象

效果验证 #

运行测试代码会输出5轮无重复搭档的配对结果，所有选手每轮都能参赛，且不会出现重复搭档的情况。

内容的提问来源于stack exchange，提问作者AwaX