秘密圣诞老人算法

Question

每逢圣诞节,我们都会在家里为礼物换取名字.这通常涉及多次重绘,直到没有人拉他们的配偶.因此,今年我编写了自己的名字绘图应用程序,其中包含一堆名称,一堆不允许的配对,并向所有人发送电子邮件与他们选择的礼品.

现在,算法就像这样(在伪代码中):

function DrawNames(list allPeople, map disallowedPairs) returns map
    // Make a list of potential candidates
    foreach person in allPeople
        person.potentialGiftees = People
        person.potentialGiftees.Remove(person)
        foreach pair in disallowedPairs
            if pair.first = person
               person.Remove(pair.second)

    // Loop through everyone and draw names
    while allPeople.count > 0
        currentPerson = allPeople.findPersonWithLeastPotentialGiftees
        giftee = pickRandomPersonFrom(currentPerson.potentialGiftees)
        matches[currentPerson] = giftee
        allPeople.Remove(currentPerson)
        foreach person in allPeople
            person.RemoveIfExists(giftee)

    return matches

知道更多关于图论的人是否知道某种算法在这里会更好用？为了我的目的,这是有效的,但我很好奇.

编辑:由于电子邮件不久前出现了,我只是希望学习一些东西,我将其重新描述为图论问题.我对排除所有成对的特殊情况不太感兴趣(如配偶没有相互获得).我对那些有足够排除条件的情况更感兴趣,因为找到任何解决方案都会成为困难的部分.我上面的算法只是一个简单的贪心算法,我不确定在所有情况下都会成功.

从完整的有向图和顶点对列表开始.对于每个顶点对,删除第一个顶点到第二个顶点的边.

目标是得到一个图形,其中每个顶点有一条边进入,一条边离开.

Answer 1

如果允许他们分享礼物然后使用完美的匹配算法,只需创建一个边缘连接两个人的图形.(寻找(聪明)算法的"路径,树和花")

Answer 2

我不会使用不允许的配对,因为这会大大增加问题的复杂性.只需将每个人的姓名和地址输入一个列表即可.创建列表的副本并保持混洗,直到两个列表的每个位置中的地址不匹配.这将确保没有人得到自己或他们的配偶.

作为奖励,如果你想做这个秘密选票风格,打印第一个列表中的信封和第二个列表中的名称.塞满信封时不要偷看.(或者你可以自动通过电子邮件发送给所有人.)

在这个线程上有更多解决方案可以解决这个问题.

Answer 3

我自己就是这样做的,最后我使用的算法并没有用帽子精确地模拟绘图名称,但它非常接近.基本上将列表洗牌,然后将每个人与列表中的下一个人配对.与帽子名称的唯一区别在于,您获得一个周期,而不是可能获得仅相互交换礼物的迷你子组.如果有什么可能是一个功能.

在Python中实现:

import random
from collections import deque
def pairup(people):
    """ Given a list of people, assign each one a secret santa partner
    from the list and return the pairings as a dict. Implemented to always
    create a perfect cycle"""
    random.shuffle(people)
    partners = deque(people)
    partners.rotate()
    return dict(zip(people,partners))

Answer 4

嗯.我参加了图论的课程,但更简单的是随机排列你的列表,配对每个连续的组,然后交换任何不允许的元素与另一个.由于任何给定对中没有不允许的人,如果您不允许与所选组进行交换,则交换将始终成功.你的算法太复杂了.