26

每年圣诞节，我们都会为我家的礼物交换画名字。这通常涉及多次重绘，直到没有人拉他们的配偶。所以今年我编写了自己的名字绘图应用程序，它接收一堆名字，一堆不允许的配对，并向每个人发送一封电子邮件，以及他们选择的礼物。

现在，算法是这样工作的（在伪代码中）：

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

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

编辑：由于电子邮件不久前发出，我只是希望能学到一些东西，我将把它改写为一个图论问题。我对排除都是配对的特殊情况不感兴趣（比如配偶没有得到对方）。我对有足够的排除项以找到任何解决方案成为困难部分的情况更感兴趣。我上面的算法只是一个简单的贪心算法，我不确定在所有情况下都会成功。

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

目标是得到一个图，其中每个顶点都有一条边进入，一条边离开。

4

9 回答 9

10

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

于 2008-11-07T22:14:23.587 回答
8

我自己只是这样做，最后我使用的算法并不能完全模拟绘图名称，但它非常接近。基本上打乱列表，然后将每个人与列表中的下一个人配对。从帽子中抽出名字的唯一区别是，你得到一个循环，而不是可能得到只相互交换礼物的小型小组。如果有什么可能是一个功能。

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))
于 2008-11-19T21:43:17.770 回答
6

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

作为奖励，如果您想进行这种无记名投票方式，请打印第一个列表中的信封和第二个列表中的姓名。装信封时不要偷看。（或者你可以自动向他们选择的每个人发送电子邮件。）

在这个线程上有更多解决这个问题的方法。

于 2008-11-07T20:37:28.137 回答
5

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

于 2008-11-07T20:40:28.800 回答
2

创建一个图，其中每条边都是“礼物性”代表配偶的顶点不会相邻。随机选择一条边（即礼物分配）。删除所有来自送礼者的边和所有去往接收者的边并重复。

于 2010-11-10T20:57:13.937 回答
2

图论中有一个概念称为哈密顿电路，它描述了您描述的“目标”。任何发现这一点的人的一个提示是告诉用户使用哪个“种子”来生成图表。这样，如果您必须重新生成图表，您可以。如果您必须添加或删除一个人，“种子”也很有用。在这种情况下，只需选择一个新的“种子”并生成一个新图表，确保告诉参与者哪个“种子”是当前/最新的。

于 2011-12-31T06:33:49.003 回答
1

我刚刚创建了一个可以做到这一点的网络应用程序 - http://www.secretsantaswap.com/

我的算法允许子组。它不漂亮，但它有效。

操作如下：
1. 为所有参与者分配一个唯一标识符，记住他们在哪个子组
2. 复制并打乱该列表（目标）
3. 创建每个子组中参与者数量的
数组 4. 复制数组[3] 用于目标
5. 创建一个新数组来保存最终匹配
项 6. 遍历参与者分配不符合以下任何条件的第一个目标：
     A. 参与者 == 目标
     B. 参与者.子组 == 目标.子组C.
     选择目标将导致子组在未来失败（例如，子组 1 必须始终保留至少与子组 1 参与者剩余的参与者一样多的非子组 1 目标）
     D.参与者（n + 1）==目标（n + 1）
如果我们分配目标，我们还将数组从3和4递减

所以，（一点也不）漂亮，但它有效。希望能帮助到你，

丹·卡尔森

于 2008-11-28T15:39:01.687 回答
1

这是秘密圣诞老人问题的简单java实现。

public static void main(String[] args) {
    ArrayList<String> donor = new ArrayList<String>();
    donor.add("Micha");
    donor.add("Christoph");
    donor.add("Benj");
    donor.add("Andi");
    donor.add("Test");
    ArrayList<String> receiver = (ArrayList<String>) donor.clone();

    Collections.shuffle(donor);
    for (int i = 0; i < donor.size(); i++) {
        Collections.shuffle(receiver);
        int target = 0;
        if(receiver.get(target).equals(donor.get(i))){              
            target++;
        }           
        System.out.println(donor.get(i) + " => " + receiver.get(target));
        receiver.remove(receiver.get(target));
    }
}
于 2012-10-11T12:50:29.397 回答
0

Python解决方案在这里。

给定一个 的序列(person, tags)，其中标签本身是一个（可能为空的）字符串序列，我的算法建议一个人链，其中每个人给链中的下一个人礼物（最后一个人显然与第一个人配对）。

存在标签以便可以对人进行分组，并且每次从最不加入的组中选择下一个人时，最后选择的人。初始人员由一组空标签选择，因此将从最长的组中选择。

因此，给定一个输入序列：

example_sequence= [
    ("person1", ("male", "company1")),
    ("person2", ("female", "company2")),
    ("person3", ("male", "company1")),
    ("husband1", ("male", "company2", "marriage1")),
    ("wife1", ("female", "company1", "marriage1")),
    ("husband2", ("male", "company3", "marriage2")),
    ("wife2", ("female", "company2", "marriage2")),
]

一个建议是：

['person1 [male,company1]', 'person2 [female,company2]', 'person3 [male,company1]', 'wife2 [female,marriage2,company2]', 'husband1 [male,marriage1,company2]', 'husband2 [男,marriage2,company3]', 'wife1 [female,marriage1,company1]']

当然，如果所有人都没有标签（例如一个空元组），那么只有一组可供选择。

并不总是有最佳解决方案（想想 10 名女性和 2 名男性的输入序列，他们的类型是唯一给出的标签），但它尽其所能地做得很好。

Py2/3 兼容。

import random, collections

class Statistics(object):
    def __init__(self):
        self.tags = collections.defaultdict(int)

    def account(self, tags):
        for tag in tags:
            self.tags[tag] += 1

    def tags_value(self, tags):
        return sum(1./self.tags[tag] for tag in tags)

    def most_disjoined(self, tags, groups):
        return max(
            groups.items(),
            key=lambda kv: (
                -self.tags_value(kv[0] & tags),
                len(kv[1]),
                self.tags_value(tags - kv[0]) - self.tags_value(kv[0] - tags),
            )
        )

def secret_santa(people_and_their_tags):
    """Secret santa algorithm.

    The lottery function expects a sequence of:
    (name, tags)

    For example:

    [
        ("person1", ("male", "company1")),
        ("person2", ("female", "company2")),
        ("person3", ("male", "company1")),
        ("husband1", ("male", "company2", "marriage1")),
        ("wife1", ("female", "company1", "marriage1")),
        ("husband2", ("male", "company3", "marriage2")),
        ("wife2", ("female", "company2", "marriage2")),
    ]

    husband1 is married to wife1 as seen by the common marriage1 tag
    person1, person3 and wife1 work at the same company.
    …

    The algorithm will try to match people with the least common characteristics
    between them, to maximize entrop— ehm, mingling!

    Have fun."""

    # let's split the persons into groups

    groups = collections.defaultdict(list)
    stats = Statistics()

    for person, tags in people_and_their_tags:
        tags = frozenset(tag.lower() for tag in tags)
        stats.account(tags)
        person= "%s [%s]" % (person, ",".join(tags))
        groups[tags].append(person)

    # shuffle all lists
    for group in groups.values():
        random.shuffle(group)

    output_chain = []
    prev_tags = frozenset()
    while 1:
        next_tags, next_group = stats.most_disjoined(prev_tags, groups)
        output_chain.append(next_group.pop())
        if not next_group:  # it just got empty
            del groups[next_tags]
            if not groups: break
        prev_tags = next_tags

    return output_chain

if __name__ == "__main__":
    example_sequence = [
        ("person1", ("male", "company1")),
        ("person2", ("female", "company2")),
        ("person3", ("male", "company1")),
        ("husband1", ("male", "company2", "marriage1")),
        ("wife1", ("female", "company1", "marriage1")),
        ("husband2", ("male", "company3", "marriage2")),
        ("wife2", ("female", "company2", "marriage2")),
    ]
    print("suggested chain (each person gives present to next person)")
    import pprint
    pprint.pprint(secret_santa(example_sequence))
于 2017-11-24T18:00:24.193 回答