如何避免秘密圣诞老人算法中出现剩余单个姓名的问题？

问题回顾 #

我想写程序自动化家庭秘密圣诞老人抽签，用邮件通知每个人抽到的对象且不被他人知晓。最初写的代码遍历每个姓名，从排除自己的未选名单里随机选，但最后一个人经常会碰到剩下的只有自己的情况，3人测试时失败率约25%。代码如下：

from random import choice

names = ["Foo", "Bar", "Baz"]

unassigned = names[:]
assigned = []

for gifter in names:
    giftee = choice([n for n in unassigned if n != gifter])
    assigned.append((gifter, giftee))
    unassigned.remove(giftee)

for name, giftee in assigned:
    print(f'{name} -> {giftee}')

我的需求：

• 尽量不用捕获异常重试的方式，要确定性方案一次成功
• 保留单个分配的随机性，允许互相送礼（比如A→B、B→A），不要强制生成单一的环形链，条件逻辑对随机性影响越小越好

解决方案 #

方法一：洗牌后修正自环（简单高效） #

核心思路是先随机打乱名单，再检查并修正可能出现的自环（即某人抽到自己的情况），这种方法随机性损失极小，且逻辑简单：

from random import shuffle

names = ["Foo", "Bar", "Baz"]
shuffled = names.copy()
shuffle(shuffled)

# 检查并修正自环
for i in range(len(shuffled)):
    if shuffled[i] == names[i]:
        if i != len(shuffled) - 1:
            # 非最后一个元素，和下一个交换
            shuffled[i], shuffled[i+1] = shuffled[i+1], shuffled[i]
        else:
            # 最后一个元素，和第一个交换
            shuffled[i], shuffled[0] = shuffled[0], shuffled[i]

# 生成分配结果
assigned = list(zip(names, shuffled))

for gifter, giftee in assigned:
    print(f'{gifter} -> {giftee}')

方法二：迭代分配时提前规避最后冲突 #

如果想保留原有的遍历分配逻辑，可以在倒数第二步时提前检查，避免最后只剩自己的情况：

from random import choice

names = ["Foo", "Bar", "Baz"]
unassigned = names.copy()
assigned = []

for idx, gifter in enumerate(names):
    # 处理最后一个人：直接取剩下的（前面的分配已经确保剩下的不是自己）
    if idx == len(names) - 1:
        giftee = unassigned[0]
    else:
        candidates = [n for n in unassigned if n != gifter]
        # 检查：如果当前可选只剩一个，且这个是下一个人，会导致下一个人只能选自己
        if len(candidates) == 1 and candidates[0] == names[idx+1]:
            # 换个思路：找前面已经分配过的人，交换他们的目标
            for j in range(idx):
                if assigned[j][1] != gifter:
                    # 把前面人的目标换成当前唯一候选，当前人选前面人的原目标
                    assigned[j] = (assigned[j][0], candidates[0])
                    giftee = assigned[j][1]
                    break
        else:
            giftee = choice(candidates)
    
    assigned.append((gifter, giftee))
    unassigned.remove(giftee)

for gifter, giftee in assigned:
    print(f'{gifter} -> {giftee}')

说明 #

• 方法一的随机性几乎和普通洗牌一致，只有在出现自环时才做最小调整，完全满足需求
• 方法二更贴近原有的遍历逻辑，但代码稍复杂，适合需要保持原流程的场景

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