Python中随机列表对比问题：抽签匹配校验实现方案

核心思路 #

先通过预处理建立快速查询的映射关系，再对生成的随机排列进行两步合规性检查，利用集合的O(1)查询特性提升效率，同时加入短路判断减少不必要的计算。

步骤拆解 #

1. 预处理映射

   • 建立「姓名→所属团队」「团队→成员列表」的映射，快速获取每个成员的同队人员。
   • 为每个姓名生成两个集合：
     • 禁止抽取的对象（自己+同队成员）
     • 禁止出现的位置（原团队对应的索引区间，比如1组的A/B不能出现在0、1位）

2. 生成随机排列
   使用random.sample(a, 6)生成全随机的抽签结果。

3. 合规性检查

   • 条件一检查：遍历每个原成员，确认其抽到的对象不在禁止列表中。
   • 条件二检查：遍历抽签结果的每个位置，确认该位置的成员不在禁止出现的位置区间内。
   • 任意条件不满足则直接返回False，全部满足返回True。

代码实现 #

import random
from collections import defaultdict

def is_valid_hat_draw(a, b):
    # 预处理团队与成员的映射关系
    team_members = defaultdict(list)
    name_to_team = {}
    for name, team in zip(a, b):
        team_members[team].append(name)
        name_to_team[name] = team
    
    # 生成每个成员的禁止抽取对象集合（自己+同队）
    forbidden_targets = {name: set(team_members[name_to_team[name]]) for name in a}
    
    # 生成每个成员的禁止出现位置集合
    team_forbidden_pos = {1: {0, 1}, 2: {2, 3}, 3: {4, 5}}
    forbidden_positions = {name: team_forbidden_pos[name_to_team[name]] for name in a}
    
    # 生成随机抽签结果
    draw_result = random.sample(a, 6)
    
    # 检查是否抽到自己或同队成员
    for idx, original_name in enumerate(a):
        if draw_result[idx] in forbidden_targets[original_name]:
            return False
    
    # 检查是否出现在禁止的位置区间
    for pos, drawn_name in enumerate(draw_result):
        if pos in forbidden_positions[drawn_name]:
            return False
    
    return True

# 测试用例
a = ["A", "B", "C", "D", "E", "F"]
b = [1, 1, 2, 2, 3, 3]
print(is_valid_hat_draw(a, b))

优化点说明 #

• 用集合存储禁止项，将成员查询的时间复杂度从O(n)降到O(1)，提升检查效率。
• 检查过程中加入短路逻辑，一旦发现违规立即返回，避免无效计算。
• 预处理逻辑与检查逻辑分离，若需多次调用可将预处理部分抽离，避免重复执行。

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