秘密のサンタアルゴリズム
https://stackoverflow.com/questions/273567
-
07-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
毎年クリスマスには、私の家族のギフト交換に名前を付けます。これは通常、誰も配偶者を引っ張らないまで複数の再描画を伴います。そのため、今年、私は自分の名前描画アプリをコーディングしました。このアプリは、名前の束、許可されていないペアの束を受け取り、選択した贈答品を持つ全員にメールを送信します。
今、アルゴリズムは次のように機能します（擬似コード）：
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つのエッジが出るグラフを取得することです。
解決
ギフトを共有することが許可されている場合、2人をつなぐエッジを使用してグラフを作成し、完全なマッチングアルゴリズムを使用します。 （（賢い）アルゴリズムの＆quot; Paths、Trees、and Flowers＆quot;を探してください）
他のヒント
許可されていないペアリングは使用しません。問題が複雑になるためです。全員の名前と住所をリストに入力するだけです。リストのコピーを作成し、2つのリストの各位置のアドレスが一致しないまでシャッフルし続けます。これにより、誰も自分や配偶者を取得できなくなります。
おまけとして、この秘密投票スタイルを行いたい場合は、最初のリストから封筒を印刷し、2番目のリストから名前を印刷します。封筒を詰めている間は覗かないでください。 （または、選択したすべての人へのメール送信を自動化することもできます。）
私はこれを自分でやっていました。結局、使用したアルゴリズムは帽子から図面名を正確にモデル化するわけではありませんが、かなり近いです。基本的にリストをシャッフルし、各人をリスト内の次の人とペアにします。帽子から名前を引き出すこととの唯一の違いは、お互いに贈り物を交換するだけの小さなサブグループを獲得する可能性の代わりに、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))
うーん。グラフ理論のコースを取りましたが、リストをランダムに並べ替え、連続する各グループをペアにしてから、許可されていない要素を別の要素と交換する方が簡単です。特定のペアには許可されていない人はいないため、選択したグループとのスワップを許可しない場合、スワップは常に成功します。アルゴリズムが複雑すぎます。
各エッジが「贈答性」であるグラフを作成します。配偶者を表す頂点は隣接しません。エッジをランダムに選択します（ギフトの割り当てです）。 Gifterからのすべてのエッジと、Receiverに向かうすべてのエッジを削除して、繰り返します。
グラフの理論には、「目標」を説明するハミルトニアンサーキットと呼ばれる概念があります。あなたが説明します。これを見つけた人にとっての1つのヒントは、どの「シード」をユーザーに伝えるかです。グラフの生成に使用されました。こうすることで、グラフを再生成する必要があります。 「シード」人を追加または削除する必要がある場合にも便利です。その場合、単に新しい「シード」を選択します。新しいグラフを生成し、どの「シード」が参加者に伝えられるようにします。現在/最新のものです。
まさにこれを行うWebアプリを作成しました- http://www.secretsantaswap.com/
私のアルゴリズムはサブグループを許可します。きれいではありませんが、動作します。
次のように動作します。
1。すべての参加者に一意の識別子を割り当て、参加しているサブグループを覚えておいてください
2。そのリスト（ターゲット）を複製してシャッフルする
3。各サブグループの参加者数の配列を作成します
4。ターゲットの[3]からの配列の複製
5。最終的な一致を保持する新しい配列を作成します
6。次の基準のいずれにも一致しない最初のターゲットを割り当てる参加者を反復処理します。
＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; A。参加者==ターゲット
＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; B。 Participant.Subgroup == target.Subgroup
＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; C。ターゲットを選択すると、サブグループが将来失敗します（たとえば、サブグループ1には、サブグループ1の参加者が残っている参加者と少なくとも同じ数の非サブグループ1のターゲットが常に残っている必要があります）
＆nbsp;＆nbsp;＆nbsp;＆nbsp;＆nbsp; D。参加者（n + 1）==ターゲット（n +1）
ターゲットを割り当てると、配列を3と4からデクリメントします
したがって、きれいではありません（まったく）が、動作します。役に立てば幸いです、
ダンカールソン
ここでは、秘密のサンタ問題のための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));
}
}
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 [male、company1]'、 'person2 [female、company2]'、 'person3 [male、company1]'、 'wife2 [female、marriage2、company2]'、 'husband1 [male、marriage1、company2]'、 'husband2 [male、marriage2、company3]'、 'wife1 [female、marriage1、company1]']
もちろん、すべての人がタグを持たない場合（空のタプルなど）、選択できるグループは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))
