गुप्त सांता एल्गोरिदम

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 

किसी को जो ग्राफ सिद्धांत के बारे में अधिक जानता है एल्गोरिथ्म है कि बेहतर यहाँ काम करेगा किसी तरह पता है? मेरे उद्देश्यों के लिए, यह काम करता है, लेकिन मैं उत्सुक हूँ।

संपादित करें: चूंकि ईमेल कुछ समय पहले बाहर निकले थे, और मैं बस कुछ सीखने की उम्मीद कर रहा हूं, मैं इसे ग्राफ़ सिद्धांत प्रश्न के रूप में दोहरा दूंगा। मुझे विशेष मामलों में इतनी दिलचस्पी नहीं है कि बहिष्कार सभी जोड़े हैं (जैसे पति/पत्नी एक दूसरे को नहीं मिल रहे हैं)। मुझे उन मामलों में अधिक दिलचस्पी है जहां पर्याप्त बहिष्कार हैं जो किसी समाधान को ढूंढना कठिन हिस्सा बन जाते हैं। उपरोक्त मेरा एल्गोरिदम सिर्फ एक साधारण लालची एल्गोरिदम है कि मुझे यकीन नहीं है कि सभी मामलों में सफल होगा।

एक पूर्ण निर्देशित ग्राफ और वर्टेक्स जोड़े की एक सूची से शुरू हो रहा है। प्रत्येक vertex जोड़ी के लिए, पहले vertex से दूसरे को किनारे को हटा दें।

लक्ष्य एक ग्राफ प्राप्त करना है जहां प्रत्येक चरम पर एक किनारे आ रहा है, और एक किनारा छोड़ रहा है।

Answer 1

अगर उन्हें उपहार साझा करने की अनुमति है और फिर एक परिपूर्ण मिलान एल्गोरिदम का उपयोग करने के लिए दो लोगों को जोड़ने वाले किनारों के साथ एक ग्राफ बनाएं। ((चालाक) एल्गोरिदम के लिए "पथ, पेड़, और फूल" की तलाश करें)

Answer 2

मैं अस्वीकृत जोड़ी का उपयोग नहीं करता, क्योंकि इससे समस्या की जटिलता बहुत बढ़ जाती है। बस सूची में सभी का नाम और पता दर्ज करें। सूची की प्रति बनाएं और इसे तब तक शफल रखें जब तक कि दो सूचियों की प्रत्येक स्थिति में पते मेल नहीं खाते। यह सुनिश्चित करेगा कि कोई भी खुद को, या उनके पति/पत्नी को नहीं ले जाएगा।

बोनस के रूप में, यदि आप यह गुप्त-मतपत्र-शैली करना चाहते हैं, तो पहली सूची से लिफाफे प्रिंट करें और दूसरी सूची के नाम प्रिंट करें। लिफाफे भरते समय झुकना मत करो। (या आप बस हर किसी को चुनने के लिए ईमेल स्वचालित कर सकते हैं।)

this thread पर इस समस्या के और भी समाधान हैं।

Answer 3

हम्म। मैंने ग्राफ सिद्धांत में एक कोर्स लिया, लेकिन सरल है कि बस अपनी सूची को यादृच्छिक रूप से अनुमति दें, प्रत्येक समूह को जोड़ दें, फिर किसी अन्य तत्व को स्वैप करें जो किसी अन्य के साथ अस्वीकृत है। चूंकि किसी दिए गए जोड़ी में कोई अस्वीकृत व्यक्ति नहीं है, इसलिए यदि आप चुने गए समूह के साथ स्वैप की अनुमति नहीं देते हैं तो स्वैप हमेशा सफल रहेगा। आपका एल्गोरिदम बहुत जटिल है।

Answer 4

मैं बस यह स्वयं कर रहा था, अंत में मैंने उपयोग किए गए एल्गोरिदम को टोपी से ड्राइंग नामों का बिल्कुल मॉडल नहीं बनाया है, लेकिन यह है बहुत बहुत करीब है। मूल रूप से सूची को घुमाएं, और फिर प्रत्येक व्यक्ति को सूची में अगले व्यक्ति के साथ जोड़ दें। एक टोपी से बाहर ड्राइंग नामों के साथ एकमात्र अंतर यह है कि आप संभावित रूप से उन लोगों के मिनी उपसमूहों को प्राप्त करने के बजाय एक चक्र प्राप्त करते हैं जो केवल एक-दूसरे के साथ उपहारों का आदान-प्रदान करते हैं। यदि कुछ भी हो सकता है जो एक सुविधा हो सकता है।

अजगर में

कार्यान्वयन: - http://www.secretsantaswap.com/

मेरे एल्गोरिथ्म उपसमूहों के लिए अनुमति देता है

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 5

मैं सिर्फ इतना है कि वास्तव में यह कर देगा एक वेब एप्लिकेशन बनाया। यह सुंदर नहीं है, लेकिन यह काम करता है।

इस प्रकार संचालित:
1. असाइन सभी प्रतिभागियों को एक अद्वितीय पहचानकर्ता, याद जो उपसमूह वे में
2. डुप्लिकेट कर रहे हैं और उस सूची (लक्ष्य) शफ़ल
3. संख्या की एक सरणी बनाने प्रत्येक उपसमूह में भाग लेने वालों की
4. से डुप्लिकेट सरणी [3] लक्ष्यों के लिए
5. अंतिम मैचों
6. पहला निशाना बताए प्रतिभागियों के माध्यम से पुनरावृति कि निम्न में से किसी से मेल नहीं खाता धारण करने के लिए एक नई सरणी बनाने मानदंड:
          ए भागीदार == लक्ष्य
          बी participant.Subgroup == target.Subgroup
          सी लक्ष्य चुनने एक उपसमूह का कारण भविष्य में विफल होगा (जैसे उपसमूह 1 चाहिए हमेशा कम से कम के रूप में कई गैर उपसमूह प्रतिभागियों के रूप में शेष 1 लक्ष्य 1 शेष प्रतिभागियों)
          डी भागीदार (n + 1) == लक्ष्य (एन उपसमूह +1)
अगर हम आवंटित लक्ष्य हम 3 और 4

से सरणी भी कम करते हैं, तो सुंदर नहीं (बिल्कुल) लेकिन यह काम करता है। आशा है कि यह मदद करता है,

दान कार्लसन

Answer 6

एक ग्राफ जहां प्रत्येक किनारे "giftability" कोने कि जीवनसाथी का प्रतिनिधित्व आसन्न नहीं किया जाएगा बनाएँ। यादृच्छिक रूप से एक किनारे का चयन करें (यह एक उपहार असाइनमेंट है)। गिफ्ट से आने वाले सभी किनारों और रिसीवर पर जाने वाले सभी किनारों को हटाएं और दोहराएं।

Answer 7

ग्राफ सिद्धांत में एक अवधारणा है जिसे Hamiltonian Circuit कहा जाता है जो आपके द्वारा वर्णित "लक्ष्य" का वर्णन करता है। किसी को भी यह पता लगाने वाले लोगों के लिए एक युक्ति यह है कि ग्राफ को उत्पन्न करने के लिए "बीज" का उपयोग किया गया था। इस तरह यदि आपको ग्राफ को फिर से उत्पन्न करना है तो आप कर सकते हैं। यदि आपको किसी व्यक्ति को जोड़ना या निकालना है तो "बीज" भी उपयोगी होता है। उस मामले में बस एक नया "बीज" चुनें और एक नया ग्राफ उत्पन्न करें, यह सुनिश्चित करना कि प्रतिभागियों को "बीज" वर्तमान/नवीनतम है।

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 [पुरुष, कंपनी 1] ', ' पत्नी 2 [मादा, शादी 2, कंपनी 2] ', ' पति 1 [पुरुष, शादी 1, कंपनी 2] ', ' पति 2 [पुरुष, शादी 2, कंपनी 3] ', ' पत्नी 1 [महिला, शादी 1 , कंपनी 1] ']

बेशक, अगर सभी व्यक्तियों के पास कोई टैग नहीं है (उदा। एक खाली ट्यूपल) तो वहां से चुनने के लिए केवल एक समूह है।

हमेशा एक इष्टतम समाधान नहीं होता है (सोचें कि 10 महिलाओं और 2 पुरुषों का इनपुट अनुक्रम, उनकी शैली एकमात्र टैग है), लेकिन यह उतना अच्छा काम करता है जितना वह कर सकता है।

पीई 2/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))