最适合人们从明确的项目列表中选择的算法，其中每个项目只有一个可用？

Question

女士们先生们，

我和我最好的 friend 每年都会进行“ secret 圣诞老人”式的礼物交换，今年我一直在想一些方法让它变得有趣。我们有六个人参与，我想设计一个小程序，让我们六个人将他们最喜欢的礼物接收者以及他们最喜欢的礼物赠送者从 1 到 5 排序。

那么，假设我们叫 A、B、C、D、E 和 F。

A提交两个列表:

List 1 - People I would most like to give a present to: B, D, C, F, E

List 2 - People I would most like to recieve a present from: F, D, E, B, C

我们六个人都会提交这两个列表，所以我总共有 12 个列表。我想我的问题是现在继续为每个人分配一个礼物接收者的最佳算法是什么？

我想到了这样的事情:

如果两个人都在他们的反对列表中选择了对方(即 A 最想给 B，B 最想从 A 得到)那么我立即将 A 分配给 B。所以现在 A 从我们的列表中删除礼物收件人和 B 从我们的礼物赠送者池中删除。

一旦我分配了“完美匹配”，我就有点迷茫了，有没有针对这种情况的建立算法？显然它只是为了娱乐值(value)，但肯定必须有类似东西的“真实”应用吗？也许是时间表之类的？

我的 Google-fu 失败了，但我觉得这可能只是因为我自己在搜索词方面不够精确。

干杯，(我想是节日快乐)，罗布

---

更新/第 2 部分

好的，Ying Xiao通过推荐 Gale Shapley Algorithm 来拯救对于 Stable Marriage Problem我已经在 Python 中实现了它，而且效果很好。然而，这只是我的一个想法。我想在我们六个最好的 friend 中，有三对“特别好的” friend ，所以我觉得我们最终会得到三对 AB、CD、EF 和 BA、DC、FE 作为礼物给予和接受。

我们是否可以设计一种算法，既考虑到人们的排名，又限制两个人组成“封闭组”？也就是说，如果 A 被分配给 B 买礼物，B 不能被分配给 A 买礼物吗？也许我需要解决 Stable roommates problem ？

相关问题:

• Secret santa algorithm.
• What is the best low-tech protocol to simulate drawing names out of a hat and ensure secrecy?

Answer 1

Gale-Shapley 算法(针对稳定婚姻问题)仅适用于每个人都有所有其他参与者的排名列表时——您可能会也可能不会将您的问题转换为该形式(让每个人都排名 每个人)。

另外，请注意，它优化的对象是不同的:它试图找到一组稳定的婚姻，其中没有一对人会“私奔”，因为他们更喜欢彼此而不是他们的目前的合作伙伴。这不是您在 Secret Santa 应用程序中关心的事情。

您想要的(取决于您对“最佳”的定义)是最大权重二分匹配，它解决了上述两个反对意见:将“给予者”放在一边，将“接受者”放在一边” 另一方面(在这种情况下，每个人都有两个副本)，根据给予者对接受者的排名，为每条边赋予权重，现在是 assignment problem .您可以使用 Hungarian algorithm为此，或更简单(较慢)的。您还可以改变分配权重的方式以针对不同的事物进行优化(例如，最大化获得第一选择的人数，或最小化任何人获得的最差选择等)

如果你确实使用了 Gale-Shapley 稳定婚姻算法，请注意它对“提议者”是最优的(男性最优和女性最悲观)，所以一定要将“给予者”作为“提议者”，反之亦然。