Python秘密圣诞老人计划-如何获得更高的成功率

Question

我决定制作一个Python程序，根据硬编码限制（例如，某人不能得到他的妻子）生成秘密圣诞老人配对。我的家人都很忙，所以很难组织每个人随机画帽子。

我的程序崩溃seldomly，因为不幸的随机配对使剩余的不合法（然而，我抓住他们在测试脚本部分）。把它想象成一个重新绘制的人。

然而，当我的程序成功时，我知道配对是正确的，而不必亲自查看它们，因为我的程序测试有效性。明天，我将不得不找到一种方法，使用配对从我的电子邮件账户给每个人发一封电子邮件，告诉他们有谁，而我不知道谁有谁，甚至谁有我。

以下是我完整的程序代码（所有代码都是我自己的；我没有在网上查找任何解决方案，因为我想自己接受最初的挑战）：

# 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", "[e-mail]")
me = Person("Me", "[e-mail]")
brother2 = Person("Brother2", "[e-mail]")
brother2Girlfriend = Person("Brother2Girlfriend", "[e-mail]")
brother3 = Person("Brother3", "[e-mail]")
brother3Girlfriend = Person("Brother3Girlfriend", "[e-mail]")
brother4 = Person("Brother4", "[e-mail]")
brother4Girlfriend = Person("Brother4Girlfriend", "[e-mail]")
brother5 = Person("Brother5", "[e-mail]")
brother5Girlfriend = Person("Brother5Girlfriend", "[e-mail]")
myDad = Person("MyDad", "[e-mail]")
myDad.isAllowedToHaveSecretSanta = False
myMom = Person("MyMom", "[e-mail]")
myMom.isAllowedToHaveSecretSanta = False
dadOfBrother4Girlfriend = Person("DadOfBrother4Girlfriend", "[e-mail]")
momOfBrother4Girlfriend = Person("MomOfBrother4Girlfriend", "[e-mail]")

# 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))

请原谅我的一些冗余代码，但我已经离开Python一段时间了，没有太多时间重新学习和研究概念。

起初，我的程序测试是这样进行的：大部分是成功的测试，0次失败（非法配对），很少崩溃（出于我上面提到的原因）。然而，那是在我的家人决定为今年的秘密圣诞老人增加新规定之前。我的妈妈可以是某人的秘密圣诞老人，爸爸也可以，但没有人可以是他们的秘密圣诞老人（因为每个人每年都给他们送礼物）。我哥哥的妻子的父母也包括在内，我哥哥、他的妻子和他妻子的父母之间不可能有任何配对。

当我加入这些新的限制规则时，我的测试大多失败，很少成功（因为随机性通常导致2到1个人在执行结束时没有秘密圣诞老人）。见下文：

秘密圣诞老人过程中设置的限制越多，解决的问题就越复杂。我渴望提高这个项目的成功率。有办法吗？在考虑秘密圣诞老人的限制时，我需要考虑哪些规则（排列或数学上常见的）？

Answer 1

这是一个二部匹配问题。您有两组节点：一组用于给予者，另一组用于接收者。每个集合中的每个人都有一个节点。如果一对是有效的，那么从给予者到接受者都有一个优势。否则就没有优势。然后应用二部匹配算法。