这里有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."""
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)
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:
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))