26

毎年クリスマスに、家族のプレゼント交換のために名前を描きます。これには通常、誰も配偶者を引っ張らなくなるまで、複数回の再描画が含まれます。そこで今年、私は独自の名前描画アプリを作成しました。このアプリは、たくさんの名前と許可されていない組み合わせを取り込んで、選択した贈り先を全員にメールで送信します。

現在、アルゴリズムは次のように機能します (疑似コード):

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

グラフ理論について詳しく知っている人は、ここでうまく機能する何らかのアルゴリズムを知っていますか? 私の目的では、これは機能しますが、興味があります。

編集: 電子メールはしばらく前に送信されたので、何かを学びたいと思っているだけなので、これをグラフ理論の質問として言い換えます。除外がすべてペアである特殊なケースにはあまり興味がありません (配偶者が互いに得られない場合など)。私は、解決策を見つけるのが難しい部分になるほどの除外がある場合にもっと興味があります。上記の私のアルゴリズムは単純な貪欲なアルゴリズムであり、すべての場合に成功するかどうかはわかりません。

完全な有向グラフと頂点ペアのリストから始めます。頂点ペアごとに、最初の頂点から 2 番目の頂点へのエッジを削除します。

目標は、各頂点に 1 つのエッジが入り、1 つのエッジが出るグラフを取得することです。

4

9 に答える 9

10

ギフトを共有することが許可されている場合は、2 人を接続するエッジを持つグラフを作成し、完全一致アルゴリズムを使用します。((巧妙な) アルゴリズムについては、「Paths, Trees, and Flowers」を探してください)

于 2008-11-07T22:14:23.587 に答える
8

私はこれを自分でやっていました.結局、私が使用したアルゴリズムは、帽子から名前を描くことを正確にモデル化しているわけではありませんが、かなり近いものです. 基本的にリストをシャッフルしてから、各人物をリスト内の次の人物とペアにします。帽子から名前を引き出すこととの唯一の違いは、お互いに贈り物を交換するだけの小さなサブグループを潜在的に得るのではなく、1 つのサイクルを得るということです。それが特徴かもしれません。

Python での実装:

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))
于 2008-11-19T21:43:17.770 に答える
6

問題の複雑さが大幅に増すため、許可されていないペアリングは使用しません。全員の名前と住所をリストに入力するだけです。リストのコピーを作成し、2 つのリストの各位置のアドレスが一致しなくなるまでシャッフルを続けます。これにより、誰も自分自身や配偶者を取得することはありません。

おまけとして、この秘密投票スタイルを行いたい場合は、最初のリストから封筒を印刷し、2 番目のリストから名前を印刷します。封筒を詰めている間はのぞかないでください。(または、選択した全員にメールを自動送信することもできます。)

このスレッドには、この問題に対するさらに多くの解決策があります。

于 2008-11-07T20:37:28.137 に答える
5

うーん。私はグラフ理論のコースを受講しましたが、より簡単なのは、リストをランダムに並べ替え、連続する各グループをペアにし、許可されていない要素を別の要素と交換することです。特定のペアに許可されていない人がいないため、選択したグループとのスワップを許可しない場合、スワップは常に成功します。アルゴリズムが複雑すぎます。

于 2008-11-07T20:40:28.800 に答える
2

グラフ理論には、ハミルトン閉路と呼ばれる概念があり、あなたが説明する「目標」を説明します。これを見つけた人へのヒントの1つは、グラフの生成にどの「シード」が使用されたかをユーザーに伝えることです。このようにして、グラフを再生成する必要がある場合に使用できます。「シード」は、人を追加または削除する必要がある場合にも役立ちます。その場合は、新しい「シード」を選択して新しいグラフを生成し、参加者にどの「シード」が現在/最新のものであるかを確認してください。

于 2011-12-31T06:33:49.003 に答える
2

各エッジが「贈与可能性」であるグラフを作成します。配偶者を表す頂点は隣接しません。エッジをランダムに選択します（つまり、ギフトの割り当てです）。贈与者からのすべてのエッジと受信者に向かうすべてのエッジを削除して、繰り返します。

于 2010-11-10T20:57:13.937 に答える
1

まさにこれを行う Web アプリを作成しました - http://www.secretsantaswap.com/

私のアルゴリズムはサブグループを許可します。きれいではありませんが、機能します。

次のように動作します:
1. すべての参加者に一意の識別子を割り当て、どのサブグループに属しているかを記憶します
2. そのリスト (ターゲット) を複製してシャッフルします
3. 各サブグループの参加者数の配列を作成します
4. から配列を複製します[3] for targets
5. 最終的な一致を保持する新しい配列を作成する
6. 次の基準のいずれにも一致しない最初のターゲットを割り当てる参加者を反復処理する:
     A. 参加者 == ターゲット
     B. 参加者.サブグループ == ターゲット.サブ
     グループ C. ターゲットを選択すると、将来サブグループが失敗する原因となります (たとえば、サブグループ 1 には、サブグループ 1 以外のターゲットが、サブグループ 1 の残りの参加者と少なくとも同じ数だけ残っている必要があります)。
     D. 参加者(n+1) == ターゲット (n +1)
ターゲットを割り当てると、配列も 3 と 4 からデクリメントされます

したがって、（まったく）きれいではありませんが、機能します。それが役に立てば幸い、

ダン・カールソン

于 2008-11-28T15:39:01.687 に答える
1

ここでは、シークレット サンタの問題に対する 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));
    }
}
于 2012-10-11T12:50:29.397 に答える