神秘圣诞老人算法 [英] Secret santa algorithm

问题描述

每到圣诞节，我们得出名字的礼物交流，我的家人。这通常需要多张重绘，直到没有人拉到自己的配偶。所以今年我codeD了我自己的名字绘图应用程序，需要在一堆名字，一串不允许配对，并发送了一封电子邮件给每个人都与他们所选择的giftee。

Every Christmas we draw names for gift exchanges in my family. This usually involves mulitple redraws until no one has pulled their spouse. So this year I coded up my own name drawing app that takes in a bunch of names, a bunch of disallowed pairings, and sends off an email to everyone with their chosen giftee.

目前，该算法是这样工作的（伪code）：

Right now, the algorithm works like this (in pseudocode):

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

有谁谁知道更多关于图论知道某种算法，将更好地工作在这里的？对于我而言，这工作，但我很好奇。

Does anyone who knows more about graph theory know some kind of algorithm that would work better here? For my purposes, this works, but I'm curious.

编辑：由于邮件出去一段时间以前，我只是希望能学到一些东西，我会改写这是一个图论的问题。我不是在特殊情况下的例外都对如此感兴趣（如配偶没有得到对方）。我更感兴趣在有足够的例外，找到任何解决方案变得困难的部分案件。上面我的算法仅仅是一个简单的贪心算法，我不知道在所有的情况下，会取得成功。

Since the emails went out a while ago, and I'm just hoping to learn something I'll rephrase this as a graph theory question. I'm not so interested in the special cases where the exclusions are all pairs (as in spouses not getting each other). I'm more interested in the cases where there are enough exclusions that finding any solution becomes the hard part. My algorithm above is just a simple greedy algorithm that I'm not sure would succeed in all cases.

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

Starting with a complete directed graph and a list of vertex pairs. For each vertex pair, remove the edge from the first vertex to the second.

的目标是获得的曲线图，其中每个顶点有一个边缘进来，和一个边缘留下

The goal is to get a graph where each vertex has one edge coming in, and one edge leaving.

推荐答案

只要有棱连接的两个人，如果他们被允许馈赠佳品，然后用一个完美的匹配算法的图。 （寻找路径，树木和鲜花为（巧）算法）

Just make a graph with edges connecting two people if they are allowed to share gifts and then use a perfect matching algorithm. (Look for "Paths, Trees, and Flowers" for the (clever) algorithm)

这篇关于神秘圣诞老人算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！