女士和男士们,
我最好的朋友和我每年都会做一次"秘密圣诞老人"类型的礼物交换,今年我一直试图想办法让它变得有趣.我们有六个人参与,我想设计一个小程序,让我们六个人将他们喜欢的礼物接受者从1到5以及他们喜欢的送礼者排名.
所以,假设我们称之为A,B,C,D,E和F.
A提交两个列表:
清单1 - 我最想给的人是:B,D,C,F,E
清单2 - 我最想收到礼物的人:F,D,E,B,C
我们所有六个人都会提交这两个列表,所以我将共有12个列表.我想我的问题是现在最好的算法是什么,并为每个人分配礼物接收者？
我想到了这样的事情:
如果两个人都在他们的对立名单中相互选择(即A最想给B,B最想从A获得)那么我立即将A分配给B.所以现在A从我们的礼物接收者列表中删除从我们的礼品赠送者中删除了B和B.
一旦我分配了"完美匹配",我有点迷失了,是否有针对这种情况的建立算法？显然它只是为了娱乐价值,但肯定必须有类似的"真实"应用吗？也许是时间表或其他什么？
我的Google-fu失败了,但我觉得这可能只是因为我自己在搜索方面缺乏精确性.
干杯,(我猜是节日快乐),Rob
好的,Ying Xiao通过推荐用于稳定婚姻问题的Gale Shapley算法来解决这个问题,我已经在Python中实现了它并且它可以实现.然而,这只是我想到的一个想法.我想在我们这六个最好的朋友中,有三对"超级好"的朋友,所以我有一种感觉,我们最终会得到三对AB,CD,EF和BA,DC,FE的礼物给予和接受.
是否有我们可以设计的算法确实考虑了人们的排名,但也限制了两个人形成一个"封闭的群体"？也就是说,如果指定A为B购买礼物,则不能指定B 为A购买礼物？也许我需要解决稳定的室友问题？
相关问题:
每年在感恩节,我的家人都会从帽子中抽出名字来确定他们将成为圣诞节礼物交换的"秘密圣诞老人".对我们的家庭文化来说,重要的是家庭中没有其他人知道对方是为了让它变得有趣而得到的.选择的唯一规则是你不能选择你的配偶.如果发生这种情况,你再次画画并将你的配偶的名字放回帽子里.
由于今年的物流和旅行计划,我们提前庆祝圣诞节(感恩节后仅两周).
为了有足够的时间寻找礼物,我们现在想选择名字.我们的家庭位于美国各地.有些成员可以上网,有些则不上网(例如亲爱的奶奶).
我想做的是有一个公平的协议,模拟从帽子中绘制名称,并确保一定程度的保密,而不是过于复杂.一些网站,如前drawames.com或其他类似的网站,通常需要人们输入他们的电子邮件地址.我想确保我家人的电子邮件地址不被滥用,所以我不想信任他们到另一个网站.
我能想出的最好的协议是:
我错过了更好的协议吗？更好的是,我的意思是允许更多保密.再次,由于物流和保持简单,我不想建立一个网站.