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 [мужчина, компания1]',
'person2 [женщина, компания2]',
'person3 [мужчина, компания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))