神秘圣诞算法

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

有没有精通图论的人知道一种可以在这里更好地工作的算法？对于我的目的，这个算法可行，但我很好奇。

编辑：由于电子邮件已经发送了一段时间，而我只是希望学到一些东西，所以我将这个问题重新表述为图论问题。我对排除所有配对的特殊情况（比如配偶不互相）不感兴趣。我更关心的是有足够多的排除条件，找到任何解决方案都变得很困难的情况。上面的算法只是一个简单的贪婪算法，我不确定它是否能在所有情况下成功。

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

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

- Josh

Answer 1

只需根据两个人是否可以共享礼物连接它们的边来制作图表，然后使用完美匹配算法。（在“路径、树和花卉”中查找（聪明的）算法）

- Watson Ladd

---

不完全正确：这是一个有向图，并且您不一定需要完美匹配；您只需要一个子图，使得每个顶点的入度=出度=1-一个循环覆盖。[有方法将其简化为完美匹配问题，但也有直接解决它的方法。] - ShreevatsaR

@ShreevatsaR：图形不必是有向的。只需为每个循环抛一枚硬币来选择方向即可。（这是假设所有被列入黑名单的对称对都是如此。） - Chris Conway

请将图视为无向图，这将排除任何二元循环，这可能是可取的。 - Chris Conway

如果黑名单对不是对称的，那怎么办？有没有相应的算法？ - Adam

Answer 2

我本来也在做这个，最后我用的算法不是模拟从帽子里抽名字，但基本上非常接近。就是将名单洗牌，然后将每个人与名单中的下一个人配对。与从帽子里抽名字的唯一区别是，你只能得到一个循环，而不是可能会有小组之间仅限于彼此交换礼物的迷你子组。如果说，这有可能成为一个特点。

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))

- wxs

Answer 3

我不会使用被禁止的配对方式，因为这会大大增加问题的复杂性。只需将每个人的姓名和地址输入到列表中。创建列表的副本并不断重排，直到两个列表中每个位置上的地址不匹配为止。这将确保没有人得到自己或自己的配偶。

作为奖励，如果您想以秘密投票的方式进行此操作，请从第一个列表中打印信封，从第二个列表中打印姓名。在装信封时不要偷看。（或者您可以自动发送电子邮件给每个人来获取他们的选择。）

在此主题上还有更多解决此问题的方法。

- Bill the Lizard

---

该程序只是向所有人发送电子邮件，因此保密性问题不是问题。 - Eclipse

那是我提到的其中一个选项。 - Bill the Lizard

Answer 4

嗯，我学过图论课程，但更简单的方法是随机排列列表，将相邻组成一对，然后将不允许的元素与另一个元素交换。由于每个给定对中都没有被禁止的人，如果不允许与所选组进行交换，则交换总会成功。你的算法太复杂了。

- Brian

---

该人及其配偶都将被禁止，因此无法保证交换操作能够成功。 - Bill the Lizard

不是真的，因为选择的组中将包括该人和他们的配偶（否则就不需要交换了）。 - Brian

Answer 5

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

- Eddie Rowe

---

这不会造成不完美的结果吗？如果送礼者有一个偏爱的受礼者怎么办？ - Dimitris Sfounis

Answer 6

图论中有一个概念叫做 哈密顿回路，它描述了你所描述的“目标”。如果需要重新生成图表，建议向用户说明使用的“种子”。这样，如果您必须重新生成图形，则可以使用相同的“种子”进行操作。如果您必须添加或删除一个人，则“种子”也很有用。在这种情况下，只需选择新的“种子”并生成一个新的图表，确保告知参与者当前/最新的“种子”即可。

- dana

Answer 7

这是一个Java语言实现的Secret Santa问题的简单示例。

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));
    }
}

- suizo

Answer 8

我刚刚创建了一个可以完全实现这一点的Web应用程序- http://www.secretsantaswap.com/

我的算法允许子组。虽然不太美观，但是能够正常运行。

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

因此，虽然不太美观，但它确实有效。希望能帮到您，

丹·卡尔森

- dancarlson

Answer 9

这里有Python的解决方案。

给定一个序列(person, tags)，其中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")),
]

一个建议是：

['人1 [男性，公司1]', '人2 [女性，公司2]', '人3 [男性，公司1]', '妻子2 [女性，婚姻2，公司2]', '丈夫1 [男性，婚姻1，公司2]', '丈夫2 [男性，婚姻2，公司3]', '妻子1 [女性，婚姻1，公司1]']

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

并不总是有最优解（考虑一个由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))

- tzot