python - 防止在 secret 圣诞老人算法中留下单个名字？

Question

今年，我决定编写一个程序，通过向每个人发送一封电子邮件，在其他人不知道的情况下，自动绘制我们家庭的 secret 圣诞老人名字图画。起初我认为这会很简单，但它给我带来了一个我不知道有效解决方案的问题。该程序会遍历每个名​​称，创建一个列表，其中包含除已分配的名称之外的所有未选取的名称，然后进行随机选择。下面是我的代码:

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}')

问题是，如果迭代的最后一个名字也是最后一个未选取的名字，那么就无法满足所需的条件。根据我的测试，上面的代码大约有 25% 的时间失败(至少有 3 个名称)。我可以做什么，或者我可以实现什么算法，以确保在迭代每个人时不会导致这些边缘情况？

我为自己制定了一些寻找解决方案的规则:

1. 如果可能的话，我不想简单地捕获异常并重复直到成功。我想找到一个确定的解决方案，保证一次运行成功。
2. 我希望为每个单独的分配保留尽可能多的熵/随机性，而不是生成单个连续的链(即，某人仍然可以向同一个人提供和从同一个人那里接收)。当然，任何添加的条件逻辑都将不可避免地在某种程度上降低这一点。

Answer 1

以下是您的问题的一种可能的解决方案:
比我想象的要长一点，但它仍然有效。 还有很多改进的空间:

代码:

from random import choice

# Generate the names in the hat
hat = ["John", "Peter", "Sam", "Susan", "Kate"]
hat_copy = hat[:]
result = []

for t in hat_copy:
    removed = False
    
    # This aims to prevent an error which occurs when the last item remains in the hat
    if len(hat) == 2 and hat_copy[-1] in hat:
        result.append(hat_copy[-1])
        hat.remove(hat_copy[-1])
        result.append(hat[0])
        hat.remove(hat[0])
        
    elif len(hat) > 0:
        # Remove t for this round (only if it exists in hat)
        if t in hat:
            hat.remove(t)
            removed = True
        
        # Select from remaining items in hat
        selection = choice(hat)
        hat.remove(selection)
        result.append(selection)
        
        # Only append t if it was removed in this round.
        if removed:
            hat.append(t)
            
    
print("Names   :", hat_copy)
print("Shuffled:", result)

输出:

Names   : ['John', 'Peter', 'Sam', 'Susan', 'Kate']
Shuffled: ['Sam', 'Kate', 'Susan', 'Peter', 'John']