Python Secret Santa-Programm - So erreichen Sie höhere Erfolgsquote

Question

Ich beschloss, ein Python Programm, das Secret Santa Paarungen basierend auf hardcoded Einschränkungen (z. B. jemand kann nicht seine Frau) zu generieren. Meine Familienmitglieder haben viel zu tun, so dass es schwierig ist, jeden zu organisieren, um eine zufällige Hutzeichnung zu machen.

Mein Programm stürzt selten wegen unglücklicher zufälliger Paarungen ab, wodurch die restlichen ILLEGAL werden (allerdings fange ich sie im Testskriptteil ein). Betrachten Sie es als eine persönliche Zeichnung.

Wenn jedoch mein Programm erfolgreich ist, weiß ich, dass die Paarungen korrekt sind, ohne dass ich sie selbst anschauen muss, weil mein Programm auf Gültigkeit testet. Morgen werde ich einen Weg finden müssen, um die Paarungen zu verwenden, um jedem eine E-Mail von meinem E-Mail-Konto zu schicken, über wen sie verfügen, ohne dass ich weiß, wer wen hat oder wer mich überhaupt hat.

Hier finden Sie meine volle Programmcode (alle Code ist meine eigene, ich keine Lösungen Online nachschlagen habe, als ich die erste Herausforderung für mich wollte):

# Imports 

import random 
import copy 
from random import shuffle 

# Define Person Class 

class Person: 
    def __init__(self, name, email): 
     self.name = name 
     self.email = email 
     self.isAllowedToHaveSecretSanta = True 
     self.isSecretSanta = False 
     self.secretSanta = None 

# ----- CONFIGURATION SCRIPT ----- 

# Initialize people objects 

brother1 = Person("Brother1", "brother1@gmail.com") 
me = Person("Me", "me@gmail.com") 
brother2 = Person("Brother2", "brother2@gmail.com") 
brother2Girlfriend = Person("Brother2Girlfriend", "brother2Girlfriend@gmail.com") 
brother3 = Person("Brother3", "brother3@gmail.com") 
brother3Girlfriend = Person("Brother3Girlfriend", "brother3Girlfriend@gmail.com") 
brother4 = Person("Brother4", "brother4@gmail.com") 
brother4Girlfriend = Person("Brother4Girlfriend", "brother4Girlfriend@gmail.com") 
brother5 = Person("Brother5", "brother5@yahoo.com") 
brother5Girlfriend = Person("Brother5Girlfriend", "brother5Girlfriend@gmail.com") 
myDad = Person("MyDad", "myDad@gmail.com") 
myDad.isAllowedToHaveSecretSanta = False 
myMom = Person("MyMom", "myMom@gmail.com") 
myMom.isAllowedToHaveSecretSanta = False 
dadOfBrother4Girlfriend = Person("DadOfBrother4Girlfriend", "dadOfBrother4Girlfriend@gmail.com") 
momOfBrother4Girlfriend = Person("MomOfBrother4Girlfriend", "momOfBrother4Girlfriend@gmail.com") 

# Initialize list of people 

personList = [brother1, 
       me, 
       brother2, 
       brother2Girlfriend, 
       brother3, 
       brother3Girlfriend, 
       brother4, 
       brother4Girlfriend, 
       brother5, 
       brother5Girlfriend, 
       myDad, 
       myMom, 
       dadOfBrother4Girlfriend, 
       momOfBrother4Girlfriend] 

# Initialize pairing restrictions mapping 
# This is a simple dictionary where the key 
# is a person and the value is a list of people who 
# can't be that person's secret santa (they might 
# be mom, girlfriend, boyfriend, or any reason) 

restrictionsMapping = {brother1.name: [], 
         me.name: [], #anybody can be my secret santa 
         brother2.name: [brother2Girlfriend.name], 
         brother2Girlfriend.name: [brother2.name], 
         brother3.name: [brother3Girlfriend.name], 
         brother3Girlfriend.name: [brother3.name], 
         brother4.name: [brother4Girlfriend.name, dadOfBrother4Girlfriend.name, momOfBrother4Girlfriend.name], 
         brother4Girlfriend.name: [brother4.name, dadOfBrother4Girlfriend.name, momOfBrother4Girlfriend.name], 
         brother5.name: [brother5Girlfriend.name], 
         brother5Girlfriend.name: [brother5.name], 
         dadOfBrother4Girlfriend.name: [momOfBrother4Girlfriend.name, brother4Girlfriend.name, brother4.name], 
         momOfBrother4Girlfriend.name: [dadOfBrother4Girlfriend.name, brother4Girlfriend.name, brother4.name]} 

# Define Secret Santa Class (Necessary for testing script) 

class SecretSantaPairingProcess: 

    # INITIALIZER 

    def __init__(self, personList, restrictionsMapping): 
     self.personList = copy.deepcopy(personList) 
     self.restrictionsMapping = restrictionsMapping 
     self.isValid = True 

    # INSTANCE METHODS 

    # Define a method that generates the list of eligible secret santas for a person 
    def eligibleSecretSantasForPerson(self, thisPerson): 
     # instantiate a list to return 
     secretSantaOptions = [] 
     for thatPerson in self.personList: 
      isEligible = True 
      if thatPerson is thisPerson: 
       isEligible = False 
       # print("{0} CAN'T receive from {1} (can't receive from self)".format(thisPerson.name, thatPerson.name)) 
      if thatPerson.name in self.restrictionsMapping[thisPerson.name]: 
       isEligible = False 
       # print("{0} CAN'T receive from {1} (they're a couple)".format(thisPerson.name, thatPerson.name)) 
      if thatPerson.isSecretSanta is True: 
       isEligible = False 
       # print("{0} CAN'T receive from {1} ({1} is alrady a secret santa)".format(thisPerson.name, thatPerson.name)) 
      if isEligible is True: 
       # print("{0} CAN receive from {1}".format(thisPerson.name, thatPerson.name)) 
       secretSantaOptions.append(thatPerson) 
     # shuffle the options list we have so far 
     shuffle(secretSantaOptions) 
     # return this list as output 
     return secretSantaOptions 

    # Generate pairings 
    def generatePairings(self): 
     for thisPerson in self.personList: 
      if thisPerson.isAllowedToHaveSecretSanta is True: 
       # generate a temporary list of people who are eligible to be this person's secret santa 
       eligibleSecretSantas = self.eligibleSecretSantasForPerson(thisPerson) 
       # get a random person from this list 
       thatPerson = random.choice(eligibleSecretSantas) 
       # make that person this person's secret santa 
       thisPerson.secretSanta = thatPerson 
       thatPerson.isSecretSanta = True 
       # print for debugging/testing 
       # print("{0}'s secret santa is {1}.".format(thisPerson.name, thatPerson.name)) 

    # Validate pairings 
    def validatePairings(self): 
     for person in self.personList: 
      if person.isAllowedToHaveSecretSanta is True: 
       if person.isSecretSanta is False: 
         # print("ERROR - {0} is not a secret santa!".format(person.name)) 
         self.isValid = False 
       if person.secretSanta is None: 
        # print("ERROR - {0} does not have a secret santa!".format(person.name)) 
        self.isValid = False 
       if person.secretSanta is person: 
        self.isValid = False 
       if person.secretSanta.name in self.restrictionsMapping[person.name]: 
        self.isValid = False 
       for otherPerson in personList: 
        if (person is not otherPerson) and (person.secretSanta is otherPerson.secretSanta): 
         # print("ERROR - {0}'s secret santa is the same as {1}'s secret santa!".format(person.name, otherPerson.name)) 
         self.isValid = False 


# ----- EXECUTION SCRIPT ----- 

### Generate pairings 
## 
##secretSanta = SecretSantaPairingProcess(personList, restrictionsMapping) 
##secretSanta.generatePairings() 
## 
### Validate results 
## 
##secretSanta.validatePairings() 
##if secretSanta.isValid is True: 
## print("This is valid") 
##else: 
## print("This is not valid") 

# ----- TESTING SCRIPT ----- 

successes = 0 
failures = 0 
crashes = 0 
successfulPersonLists = [] 

for i in range(1000): 
    try: 
     secretSanta = SecretSantaPairingProcess(personList, restrictionsMapping) 
     secretSanta.generatePairings() 
     secretSanta.validatePairings() 
     if secretSanta.isValid is True: 
      # print("This is valid") 
      successes += 1 
      successfulPersonLists.append(secretSanta.personList) 
     else: 
      # print("This is not valid") 
      failures += 1 
    except: 
     crashes += 1 
    print("Finished test {0}".format(i)) 

print("{0} successes".format(successes)) 
print("{0} failures".format(failures)) 
print("{0} crashes".format(crashes)) 

for successList in successfulPersonLists: 
    print("----- SUCCESS LIST -----") 
    for successPerson in successList: 
     if successPerson.isAllowedToHaveSecretSanta is True: 
      print("{0}'s secret santa is {1}".format(successPerson.name, successPerson.secretSanta.name)) 
     else: 
      print("{0} has no secret santa".format(successPerson.name)) 

Verzeihen Sie mir für einige redundanten Code , aber ich war eine Weile von Python weg und hatte nicht viel Zeit, Konzepte neu zu lernen und neu zu erforschen.

Zuerst gingen meine Programmtests wie folgt: Meist erfolgreiche Tests, 0 Fehler (illegale Paarungen) und selten Abstürze (aus dem oben genannten Grund). Das war jedoch bevor meine Familie beschloss, neue Regeln für den diesjährigen Secret Santa hinzuzufügen. Meine Mutter könnte jemandes geheimer Weihnachtsmann sein, und Papa könnte auch so sein, aber KEINER könnte einer ihrer Geheimen Sankt sein (da jeder sie jedes Jahr Geschenke bekommt). Die Eltern meines Bruders sollten ebenfalls aufgenommen werden, und es gab keine Paarungen zwischen meinem Bruder, seiner Frau und den Eltern seiner Frau.

Als ich diese neuen Restriktionsregeln einsetzte, ergaben meine Tests hauptsächlich Fehler und sehr wenige Erfolge (da Zufälligkeit normalerweise dazu führte, dass 2 oder 1 Personen am Ende der Ausführung keinen geheimen Weihnachtsmann hatten). Siehe unten:

Je mehr Einschränkungen, die in dem Wichteln Prozess platziert sind, desto komplexer wird das Problem lösen werden. Ich bin daran interessiert, die Erfolgsquote dieses Programms zu verbessern. Gibt es einen Weg? Gibt es Regeln (permutational oder mathematisch üblich), die ich berücksichtigen muss, wenn ich die Einschränkungen von Secret Santa bedenke?

Answer 1

Dies ist ein bipartite matching problem. Sie haben zwei Knotengruppen: eine für Geber und eine für Empfänger. Jeder Satz hat einen Knoten für jede Person in Ihrer Familie. Es gibt eine Kante von einem Geber zum Empfänger, wenn dieses Paar gültig ist. Sonst gibt es keine Kante. Wenden Sie dann den bipartiten Matching-Algorithmus an.