파이썬 솔루션은 여기에 있습니다.
태그가 자체 문자열 (아마도 비어있는) 문자열 인 경우 (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 [남성 company1]'[여성 company2] PERSON2 ' , 'person3 [남성, 회사 1] ', 'wife2 [여성, 결혼 2, 회사 2] ', '남편 1 [남성, 결혼 1, 회사 2] ', '남편 2 [남성, 결혼 2, 회사 3] ', 'wife1 [여성, 결혼 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))
그게 내가 찾고 있던거야! 감사! – Eclipse
그렇지 않습니다. 그것은 지향적 인 그래프이며 반드시 완벽하게 일치하는 것을 원하지는 않습니다. 당신은 모든 정점이 indegree = outdegree = 1 * a * cycle cover *를 갖도록 서브 그래프를 원할뿐입니다. [완벽하게 일치하는 문제로 줄이는 방법이 있지만 직접 해결할 수있는 방법이 있습니다.] – ShreevatsaR
@ShreevatsaR : 그래프를 그리지 않아도됩니다. 동전을 뒤집어서 각 사이클의 방향을 선택하십시오. (이것은 모든 블랙리스트에있는 쌍이 대칭이라고 가정합니다.) –