Python如何生成所有参与者的互斥二人完整分配组合？

核心思路 #

你需要的是生成完全图的所有完美匹配——也就是每个参与者恰好分到一组二人配对的全部方案。首先要明确：只有当参与者数量N为偶数时才有解，奇数情况下直接返回空列表即可。

最优实现方式是递归回溯：固定第一个未配对的元素，与剩余未配对元素逐一组合，再递归处理剩下的元素。这种方法能自动避免重复生成等价方案（比如不会把[(1,2),(3,4)]和[(3,4),(1,2)]视为不同方案），减少冗余计算。

代码实现 #

from itertools import combinations

def generate_all_pairings(participants):
    participants = sorted(participants)
    n = len(participants)
    if n % 2 != 0:
        return []  # 奇数个参与者无法完成完全配对
    
    def backtrack(remaining):
        if not remaining:
            yield []
            return
        # 固定第一个未配对元素，遍历所有可能的配对对象
        first = remaining[0]
        for partner in remaining[1:]:
            # 递归处理排除当前配对后的剩余元素
            rest = [x for x in remaining if x != first and x != partner]
            for sub_pairing in backtrack(rest):
                yield [(first, partner)] + sub_pairing
    
    return list(backtrack(participants))

# 示例：4个参与者的配对方案
participants = [1,2,3,4]
all_pairings = generate_all_pairings(participants)
for idx, pairing in enumerate(all_pairings, 1):
    print(f"方案{idx}: {pairing}")

关键说明 #

1. 递归的优势：通过固定第一个元素的配对对象，天然避免了重复方案，计算效率更高。
2. 大N的注意事项：如果你的N是100，要清楚完美匹配的数量是99!!（99×97×95×…×1），这个数字约为1e78，完全存储所有方案是不可能的。此时建议直接使用生成器（代码中已经用yield实现），按需迭代处理每个方案，而不是一次性转换为列表。
3. 效率优化：递归中筛选剩余元素可以改用集合提升速度，但小N场景下差异不明显；大N场景下，生成器是唯一可行的方式。

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