Python无重复配对日程优化实现及可行性计算技术问询

一、任务可行性判断 #

先明确结论：你的任务完全可行，核心原因如下：

• 参与者数量是偶数（48），每天可以刚好组成24对，没有剩余人员，满足“所有参与者两两配对”的基础要求。
• 每个参与者最多能和47个不同的人搭档（不能和自己配对），而你只需要安排30天——30远小于47，意味着每个参与者还有17次未使用的搭档机会，完全不会出现“无新搭档可选”的困境。
• 从图论角度看，这相当于在完全图K₄₈中选取30个边不重复的完美匹配：完全图总边数为48×47/2=1128，30天共需要30×24=720条边，远小于总边数，因此必然存在合法解。

二、代码优化思路与实现 #

你的现有代码依赖随机试错+重复检查，存在效率低（极端情况可能陷入死循环）、代码冗余（比如person类完全没必要，仅用到ID）的问题。下面提供两种更高效的实现方案：

方案1：经典循环赛制配对（最系统、无冲突） #

对于偶数个参与者，循环赛制可以生成所有不重复的完美匹配，逻辑简单且完全避免随机冲突，步骤如下：

1. 固定一个参与者（比如ID=0），将其他参与者排成一列。
2. 每天将列的首尾配对、中间依次配对，然后将列的最后一个元素移到最前面，生成下一天的配对。
3. 这种方式最多可生成n-1=47天的无重复配对，完全覆盖你的30天需求。

优化后的代码：

def generate_schedule(num_people, num_days):
    if num_people % 2 != 0:
        raise ValueError("参与者数量必须为偶数")
    if num_days > num_people - 1:
        raise ValueError(f"最多只能安排{num_people-1}天无重复配对")
    
    people = list(range(num_people))
    fixed_person = people[0]
    rotating_group = people[1:]
    schedule = []
    
    for _ in range(num_days):
        day_pairs = []
        # 固定人员和旋转组末尾人员配对
        day_pairs.append((fixed_person, rotating_group[-1]))
        # 旋转组首尾依次配对
        for i in range(len(rotating_group)//2):
            day_pairs.append((rotating_group[i], rotating_group[-(i+2)]))
        schedule.append(day_pairs)
        # 旋转更新：将最后一个元素移到最前面
        rotating_group = [rotating_group[-1]] + rotating_group[:-1]
    
    return schedule

# 生成并打印日程
num_people = 48
num_days = 30
schedule = generate_schedule(num_people, num_days)

print(f"{num_people} people and {num_days} days will be considered.")
for day_idx, pairs in enumerate(schedule, 1):
    print("-" * 80)
    print(f"DAY {day_idx}")
    print(", ".join(f"{a} {b}" for a, b in pairs))

方案2：高效随机配对（兼顾随机性与可靠性） #

如果希望配对结果更随机，可以提前生成所有可能的配对，再按天分配，确保每天的配对不重叠且不重复：

import itertools
import random

def generate_random_schedule(num_people, num_days):
    if num_people % 2 != 0:
        raise ValueError("参与者数量必须为偶数")
    max_possible_days = num_people - 1
    if num_days > max_possible_days:
        raise ValueError(f"最多只能安排{max_possible_days}天无重复配对")
    
    # 生成所有可能的无序配对（用frozenset避免重复记录(a,b)和(b,a)）
    all_pairs = set(frozenset((a, b)) for a, b in itertools.combinations(range(num_people), 2))
    schedule = []
    
    for _ in range(num_days):
        day_pairs = []
        used_people = set()
        # 打乱剩余配对顺序，随机选不重叠的配对
        remaining_pairs = list(all_pairs)
        random.shuffle(remaining_pairs)
        for pair in remaining_pairs:
            if not used_people.intersection(pair):
                day_pairs.append(tuple(pair))
                used_people.update(pair)
                all_pairs.remove(pair)
                if len(used_people) == num_people:
                    break
        schedule.append(day_pairs)
    
    return schedule

# 使用示例
num_people = 48
num_days = 30
schedule = generate_random_schedule(num_people, num_days)

print(f"{num_people} people and {num_days} days will be considered.")
for day_idx, pairs in enumerate(schedule, 1):
    print("-" * 80)
    print(f"DAY {day_idx}")
    print(", ".join(f"{a} {b}" for a, b in pairs))

三、核心优化点说明 #

1. 移除冗余代码：直接用整数代表参与者ID，完全不需要person类，大幅简化代码结构。
2. 避免随机试错：循环赛制从逻辑上保证无重复配对，无需额外检查；随机配对思路提前生成所有组合，按规则分配，彻底避免死循环风险。
3. 高效数据结构：用set/frozenset存储已配对组合，检查和删除操作均为O(1)，比原代码的列表检查（O(n)）效率提升显著。

内容的提问来源于stack exchange，提问作者Nicolai B. Thomsen