Python Secret Santa 程序——如何获得更高的成功率

Question

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

我的程序很少因为不幸的随机配对导致剩余的配对非法而崩溃(但是，我在测试脚本部分发现了它们)。将其视为亲自重新绘制。

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

以下是我的完整程序代码(所有代码都是我自己的，我没有在网上查找任何解决方案，因为我想自己进行初步挑战):

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

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

起初，我的程序测试是这样进行的:大部分测试成功，0 次失败(非法配对)，很少崩溃(由于我上面提到的原因)。然而，那是在我的家人决定为今年的 secret 圣诞老人添加新规则之前。我妈妈可能是某人的 secret 圣诞老人，爸爸也可能是，但没有人可以成为他们的 secret 圣诞老人(因为无论如何每个人每年都会收到礼物)。弟弟的岳 parent 也要算在内，弟弟和弟弟的岳母、岳 parent 不能成对。

当我输入这些新的限制规则时，我的测试大多失败，成功的很少(因为随机性通常会导致 2 或 1 个人在执行结束时没有 secret 圣诞老人)。见下文:

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

Answer 1

这是一个 bipartite matching problem .您有两组节点:一组用于给予者，一组用于接收者。每组都有一个节点代表您家中的每个人。如果该对有效，则从提供者到接收者之间存在一条边。否则就没有边。然后应用二分匹配算法。