خوارزمية سانتا السرية

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

هل يعرف أي شخص يعرف المزيد عن نظرية الرسم البياني نوعًا من الخوارزمية التي قد تعمل بشكل أفضل هنا؟لأغراضي، هذا يعمل، ولكن لدي فضول.

يحرر:منذ ظهور رسائل البريد الإلكتروني منذ فترة، وآمل فقط أن أتعلم شيئًا سأعيد صياغته كسؤال حول نظرية الرسم البياني.أنا لست مهتمًا جدًا بالحالات الخاصة التي تكون فيها الاستثناءات كلها أزواجًا (كما هو الحال في عدم حصول الأزواج على بعضهم البعض).أنا مهتم أكثر بالحالات التي يوجد فيها ما يكفي من الاستثناءات بحيث يصبح العثور على أي حل هو الجزء الصعب.الخوارزمية المذكورة أعلاه هي مجرد خوارزمية جشعة بسيطة لست متأكدًا من نجاحها في جميع الحالات.

البدء برسم بياني موجه كامل وقائمة بأزواج القمم.لكل زوج من القمم، قم بإزالة الحافة من الرأس الأول إلى الثاني.

الهدف هو الحصول على رسم بياني حيث يكون لكل قمة حافة واحدة قادمة وحافة واحدة تخرج.

Answer 1

وجعل مجرد رسم بياني مع حواف تربط بين الناس إذا ما سمح لهم لتبادل الهدايا ثم استخدام خوارزمية مطابقة الكمال. (ابحث عن "مسارات، الأشجار، والزهور" لذكية) خوارزمية ()

Answer 2

وأنا لن تستخدم حدودا غير مسموح بها، لأن ذلك يزيد من تعقيد المشكلة. فقط ادخل اسم الجميع وعنوان في القائمة. إنشاء نسخة من القائمة والحفاظ على خلط حتى العناوين في كل موقف من القائمتين لا تتطابق. وهذا يضمن أن لا أحد يحصل على أنفسهم، أو أزواجهن.

وعلى سبيل المكافأة، إذا كنت ترغب في القيام بذلك على غرار الاقتراع السري، طباعة المغلفات من القائمة الأولى وأسماء من القائمة الثانية. لا نظرة خاطفة في حين حشو المظاريف. (أو هل يمكن أن مجرد أتمتة البريد الإلكتروني الجميع اختيار الحية.)

وهناك أكثر حتى حلول لهذه المشكلة على <لأ href = "https://stackoverflow.com/questions/268682/what-is-the-best-low-tech-protocol-to-simulate-drawing-names -out من واحد قبعة والإلكترونية "> هذا الموضوع .

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

وإنشاء رسم بياني حيث كل حافة هو "giftability" القمم التي تمثل الزوجين لن يكون المجاورة. حدد حافة عشوائيا (أي مهمة هدية). حذف جميع حواف القادمة من gifter وجميع حواف الذهاب إلى المتلقي، وتكرار.

Answer 6

وهناك مفهوم في نظرية الرسم البياني يسمى حلبة هاملتون التي تصف "الهدف" لك وصف. طرف واحد لأي شخص يرى أن هذا هو إخبار المستخدمين التي "البذور" كان يستخدم لتوليد الرسم البياني. بهذه الطريقة إذا كان لديك لإعادة توليد-الرسم البياني يمكنك. في "المصنف" مفيد أيضا إذا كان لديك لإضافة أو إزالة شخص. في هذه الحالة مجرد اختيار "البذور" الجديد وإنشاء رسم بياني جديد، والتأكد من أن أقول المشاركين التي "البذور" هو الحالي / آخر واحد.

Answer 7

لقد قمت للتو بإنشاء تطبيق ويب يقوم بهذا بالضبط - http://www.secretsantaswap.com/

تسمح الخوارزمية الخاصة بي بالمجموعات الفرعية.إنها ليست جميلة، لكنها تعمل.

تعمل على النحو التالي:
1.قم بتعيين معرف فريد لجميع المشاركين، وتذكر المجموعة الفرعية التي ينتمون إليها
2.تكرار وخلط تلك القائمة (الأهداف)
3.إنشاء مصفوفة لعدد المشاركين في كل مجموعة فرعية
4.مجموعة مكررة من [3] للأهداف
5.إنشاء مصفوفة جديدة لعقد المباريات النهائية
6.قم بالتكرار من خلال المشاركين الذين يقومون بتعيين الهدف الأول الذي لا يتطابق مع أي من المعايير التالية:
أ.المشارك == الهدف
ب.المشاركين.المجموعة الفرعية == الهدف.المجموعة الفرعية
ج.سيؤدي اختيار الهدف إلى فشل مجموعة فرعية في المستقبل (على سبيل المثال.يجب أن يكون لدى المجموعة الفرعية 1 دائمًا ما لا يقل عن عدد من الأهداف غير التابعة للمجموعة الفرعية 1 مثل المشاركين المتبقيين في المجموعة الفرعية 1)
د.مشارك(ن+1) == هدف (ن+1)
إذا قمنا بتعيين الهدف فإننا أيضًا ننقص المصفوفات من 3 و 4

لذا، ليست جميلة (على الإطلاق) ولكنها تعمل.نأمل أن يساعد،

دان كارلسون

Answer 8

وهنا تطبيق بسيط في جافا لمشكلة سانتا السرية.

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 [الذكور، company1]'،  "PERSON2 [أنثى، company2] '،  "person3 [الذكور، company1] '،  "wife2 [أنثى، marriage2، company2] '،  "husband1 [الذكور، marriage1، company2] '،  "husband2 [الذكور، marriage2، company3] '،  "wife1 [أنثى، marriage1، company1] ']

وبطبيعة الحال، إذا كان لدى جميع الأشخاص لا العلامات (على سبيل المثال والصفوف (tuple) فارغة) ثم هناك مجموعة واحدة فقط للاختيار من بينها.

وليس هناك دائما الحل الأمثل (اعتقد تسلسل المدخلات من 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))