相关疑难解决方法(0)

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

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

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

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

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

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

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

每年在感恩节,我的家人都会从帽子中抽出名字来确定他们将成为圣诞节礼物交换的"秘密圣诞老人".对我们的家庭文化来说,重要的是家庭中没有其他人知道对方是为了让它变得有趣而得到的.选择的唯一规则是你不能选择你的配偶.如果发生这种情况,你再次画画并将你的配偶的名字放回帽子里.

由于今年的物流和旅行计划,我们提前庆祝圣诞节(感恩节后仅两周).

为了有足够的时间寻找礼物,我们现在想选择名字.我们的家庭位于美国各地.有些成员可以上网,有些则不上网(例如亲爱的奶奶).

我想做的是有一个公平的协议,模拟从帽子中绘制名称,并确保一定程度的保密,而不是过于复杂.一些网站,如前drawames.com或其他类似的网站,通常需要人们输入他们的电子邮件地址.我想确保我家人的电子邮件地址不被滥用,所以我不想信任他们到另一个网站.

我能想出的最好的协议是:

1. 编写一个随机选择人的程序,确保人们不会得到他们的配偶.
2. 该程序将向我显示列表的一半,但不会告诉我谁有我的名字,但会告诉我我的名字和得到我妻子名字的人.
3. 然后,我将离开房间,程序将向我的妻子显示另一半人名(其中包括谁有我的名字).
4. 然后我和我的妻子会联系每个人并告诉他们他们有谁.

我错过了更好的协议吗？更好的是,我的意思是允许更多保密.再次,由于物流和保持简单,我不想建立一个网站.