秘密圣诞老人算法

  • Z时代
  • 2024-01-10
  • 分类：问答

每年圣诞节，我们都会为家人的礼物交换画上名字。这通常涉及多次重划，直到没有人拉出其配偶为止。因此，今年我编写了自己的名称绘图应用程序，该应用程序接收一堆名字，一堆不允许的配对，并与选择的礼物对象发送电子邮件给所有人。

现在，该算法的工作方式如下（使用伪代码）：

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

有谁对图论了解更多的人知道某种可以在这里更好地工作的算法吗？就我的目的而言，这可行，但是我很好奇。

编辑：自从电子邮件发送了一段时间以来，我只是希望学习一些东西，我将其重新表述为图论问题。我对排除对象都是成对的特殊情况不太感兴趣（例如在配偶之间不相识）。我对有足够多的排除条件而导致找到任何解决方案变得困难的情况更感兴趣。我上面的算法只是一个简单的贪心算法，我不确定在所有情况下都能成功。

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

目的是获得一个图形，其中每个顶点都有一个边进入，一个边离开。

回答：

如果允许两个人共享礼物，只需绘制一条边缘连接两个人的图，然后使用完美的匹配算法即可。（为（聪明的）算法寻找“路径，树木和花朵”）

以上是 秘密圣诞老人算法 的全部内容， 来源链接： utcz.com/qa/409519.html

回到顶部