비밀 산타 알고리즘

Question

모든 크리스마스마다 우리는 가족의 선물 교환의 이름을 그립니다. 이것은 일반적으로 아무도 배우자를 끌어 당기지 않을 때까지 뿌리 덮개를 다시 그리기를 포함합니다. 그래서 올해 나는 많은 이름, 허용되지 않은 페어링을 많이받는 내 자신의 이름 그리기 앱을 코딩하고 선택한 선물과 함께 모든 사람에게 이메일을 보냈습니다.

현재 알고리즘은 다음과 같이 작동합니다 (의사 코드) :

function DrawNames(list allPeople, map disallowedPairs) returns map
    // Make a list of potential candidates
    foreach person in allPeople
        person.potentialGiftees = People
        person.potentialGiftees.Remove(person)
        foreach pair in disallowedPairs
            if pair.first = person
               person.Remove(pair.second)

    // Loop through everyone and draw names
    while allPeople.count > 0
        currentPerson = allPeople.findPersonWithLeastPotentialGiftees
        giftee = pickRandomPersonFrom(currentPerson.potentialGiftees)
        matches[currentPerson] = giftee
        allPeople.Remove(currentPerson)
        foreach person in allPeople
            person.RemoveIfExists(giftee)

    return matches

그래프 이론에 대해 더 많이 아는 사람이라면 여기서 더 잘 작동하는 알고리즘을 알고 있습니까? 내 목적을 위해 이것은 효과가 있지만 궁금합니다.

편집 : 이메일이 얼마 전에 나갔기 때문에, 나는 이것을 그래프 이론 질문으로 다시 표현할 것입니다. 나는 배제가 모두 쌍을 이루는 특별한 경우에 관심이 없다 (배우자는 서로를 얻지 못한다). 솔루션을 찾는 것이 어려운 부분이 된 충분한 제외가있는 경우에 더 관심이 있습니다. 위의 알고리즘은 모든 경우에 성공할 것이라고 확신하는 간단한 탐욕 알고리즘입니다.

완전한 지시 그래프 및 정점 쌍 목록으로 시작합니다. 각 정점 쌍의 경우 첫 번째 정점에서 두 번째 정점까지 가장자리를 제거하십시오.

목표는 각 정점이 하나의 가장자리가 들어오고 1 개의 가장자리가 떠나는 그래프를 얻는 것입니다.

Answer 1

선물을 공유하고 완벽한 일치 알고리즘을 사용하는 경우 두 사람을 연결하는 가장자리가있는 그래프를 만드십시오. ((영리한) 알고리즘에 대한 "길, 나무 및 꽃"을 찾으십시오)

Answer 2

나는 허용되지 않은 페어링을 사용하지 않을 것입니다. 이로 인해 문제의 복잡성이 크게 증가하기 때문입니다. 모든 사람의 이름과 주소를 목록에 입력하십시오. 목록의 사본을 만들고 두 목록의 각 위치에있는 주소가 일치하지 않을 때까지 계속 뒤섞습니다. 이것은 아무도 자신이나 배우자를 얻지 못하게 할 것입니다.

보너스로,이 비밀 균열 스타일을하고 싶다면 첫 번째 목록에서 봉투를 인쇄하고 두 번째 목록에서 이름을 인쇄하십시오. 봉투를 채우는 동안 들여다 보지 마십시오. (또는 모든 사람에게 픽을 자동으로 자동으로 자동으로 올릴 수 있습니다.)

이 문제에 대한 더 많은 해결책이 있습니다 이 스레드.

Answer 3

나는 단지 이것을 직접하고 있었는데, 결국 내가 사용한 알고리즘은 모자에서 그리기 이름을 정확하게 모델링하지는 않지만 아주 가깝습니다. 기본적으로 목록을 셔플 한 다음 각 사람을 목록의 다음 사람과 페어링하십시오. 모자에서 이름을 그리는 것과의 유일한 차이점은 서로 선물을 교환하는 사람들의 미니 하위 그룹을 잠재적으로 얻는 대신 한주기를 얻는 것입니다. 기능이 될 수 있다면.

파이썬에서의 구현 :

import random
from collections import deque
def pairup(people):
    """ Given a list of people, assign each one a secret santa partner
    from the list and return the pairings as a dict. Implemented to always
    create a perfect cycle"""
    random.shuffle(people)
    partners = deque(people)
    partners.rotate()
    return dict(zip(people,partners))

Answer 4

흠. 그래프 이론에서 과정을 밟았지만 더 간단하게 목록을 무작위로 분출하고 각 연속 그룹을 짝을 이루고 다른 사람과 허용되지 않는 요소를 교환하는 것입니다. 주어진 쌍에는 허용되지 않은 사람이 없기 때문에 선택한 그룹의 스왑을 허용하지 않으면 스왑이 항상 성공합니다. 알고리즘이 너무 복잡합니다.

Answer 5

배우자를 나타내는 "선물"정점이있는 그래프를 만듭니다. 무작위로 에지를 선택하십시오 (선물 할당). 선물에서 나오는 모든 모서리를 삭제하고 모든 가장자리가 수신기로 이동하여 반복됩니다.

Answer 6

그래프 이론에는 a라는 개념이 있습니다 해밀턴 회로 그것은 당신이 설명하는 "목표"를 설명합니다. 이것을 찾는 사람에게는 한 가지 팁이 사용자에게 그래프를 생성하는 데 어떤 "종자"가 사용되었는지 알려주는 것입니다. 이런 식으로 그래프를 다시 생성 해야하는 경우. "씨앗"은 사람을 추가하거나 제거 해야하는 경우에도 유용합니다. 이 경우 새 "시드"를 선택하고 새 그래프를 생성하여 참가자에게 어떤 "시드"가 현재/최신 정보인지 알려주십시오.

Answer 7

방금이 작업을 정확히 수행 할 웹 앱을 만들었습니다. http://www.secretsantaswap.com/

내 알고리즘을 사용하면 하위 그룹이 허용됩니다. 예쁘지는 않지만 작동합니다.

다음과 같이 작동합니다.
1. 모든 참가자에게 고유 식별자를 할당하고 어떤 하위 그룹에 있는지 기억하십시오.
2. 해당 목록을 복제하고 셔플합니다 (대상)
3. 각 하위 그룹에서 참가자 수의 배열 생성
4. 대상의 경우 [3]에서 배열을 복제합니다
5. 최종 경기를 유지하기 위해 새 배열을 만듭니다.
6. 참가자를 통한 반복은 다음 기준과 일치하지 않는 첫 번째 목표를 할당합니다.
A. 참가자 == 대상
B. 참가자 .subgroup == target.subgroup
C. 대상을 선택하면 미래에 하위 그룹이 실패하게됩니다 (예 : 하위 그룹 1은 항상 참가자 하위 그룹 1 참가자만큼 남아있는 비 탑 그룹 1 대상이 남아 있어야합니다)
D. 참가자 (n +1) == 대상 (n +1)
대상을 할당하면 배열도 3과 4에서 줄입니다.

따라서 전혀 예쁘지는 않지만 작동합니다. 도움이되기를 바랍니다.

댄 칼슨

Answer 8

여기에서 비밀 산타 문제에 대한 Java의 간단한 구현.

public static void main(String[] args) {
    ArrayList<String> donor = new ArrayList<String>();
    donor.add("Micha");
    donor.add("Christoph");
    donor.add("Benj");
    donor.add("Andi");
    donor.add("Test");
    ArrayList<String> receiver = (ArrayList<String>) donor.clone();

    Collections.shuffle(donor);
    for (int i = 0; i < donor.size(); i++) {
        Collections.shuffle(receiver);
        int target = 0;
        if(receiver.get(target).equals(donor.get(i))){              
            target++;
        }           
        System.out.println(donor.get(i) + " => " + receiver.get(target));
        receiver.remove(receiver.get(target));
    }
}

Answer 9

여기에 파이썬 솔루션.

일련의 순서가 주어졌습니다 (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 [male, company1]', 'person2 [female, company2]', 'person3 [male, company1]', 'wife2 [female, marging2, company2]', '남편 1 [남성, 결혼 1, Company2], '남편 2 [남성, 결혼 2, Company3],'아내 1 [여성, 결혼 1, Company1]]

물론, 모든 사람에게 태그가 없다면 (예 : 빈 튜플) 선택할 그룹은 하나뿐입니다.

항상 최적의 솔루션이있는 것은 아니지만 (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))