Python 秘密圣诞老人计划 - 如何获得更高的成功率
Python Secret Santa Program - How To Achieve Higher Success Rate
我决定制作一个 Python 程序，根据硬编码限制生成秘密圣诞老人配对（例如，某人无法得到他的妻子）。家里人都很忙，不好组织大家随便画个帽子。
我的程序很少崩溃，因为不幸的是随机配对使剩余的配对无效（但是，我在测试脚本部分发现了它们）。将其视为 re-drawing in-person.
但是，当我的程序成功时，我知道配对是正确的，而不必亲自查看它们，因为我的程序测试了有效性。明天，我将不得不找到一种方法来使用配对从我的电子邮件帐户向每个人发送一封关于他们拥有谁的电子邮件，而我不知道谁拥有谁，甚至谁拥有我。
以下是我的完整程序代码（所有代码都是我自己的；我没有在网上查找任何解决方案，因为我想自己进行初步挑战）：
# 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 一段时间并且没有太多时间重新学习和 re-research 概念。
起初，我的程序测试是这样进行的：大部分测试成功，0 次失败（非法配对），很少崩溃（由于我上面提到的原因）。然而，那是在我的家人决定为今年的秘密圣诞老人添加新规则之前。我妈妈可能是某人的秘密圣诞老人，爸爸也可能是，但没有人可以成为他们的秘密圣诞老人（因为无论如何每个人每年都会收到礼物）。我弟媳妇的parents也算在内，我弟和他嫂子的parents.
不能配对
当我输入这些新的限制规则时，我的测试大多失败，成功的很少（因为随机性通常会导致 2 或 1 个人在执行结束时没有秘密圣诞老人）。见下文：
Secret Santa 流程中的限制越多，要解决的问题就越复杂。我渴望提高这个项目的成功率。有办法吗？在考虑秘密圣诞老人限制时，我需要考虑哪些规则（排列的或数学上常见的）？
这是一个bipartite matching problem。您有两组节点：一组用于给予者，一组用于接收者。每组都有一个节点代表您家中的每个人。如果该对有效，则从提供者到接收者之间存在一条边。否则就没有边。然后应用二分匹配算法。
我决定制作一个 Python 程序，根据硬编码限制生成秘密圣诞老人配对（例如，某人无法得到他的妻子）。家里人都很忙，不好组织大家随便画个帽子。
我的程序很少崩溃，因为不幸的是随机配对使剩余的配对无效（但是，我在测试脚本部分发现了它们）。将其视为 re-drawing in-person.
但是，当我的程序成功时，我知道配对是正确的，而不必亲自查看它们，因为我的程序测试了有效性。明天，我将不得不找到一种方法来使用配对从我的电子邮件帐户向每个人发送一封关于他们拥有谁的电子邮件，而我不知道谁拥有谁，甚至谁拥有我。
以下是我的完整程序代码（所有代码都是我自己的；我没有在网上查找任何解决方案，因为我想自己进行初步挑战）：
# 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 一段时间并且没有太多时间重新学习和 re-research 概念。
起初，我的程序测试是这样进行的：大部分测试成功，0 次失败（非法配对），很少崩溃（由于我上面提到的原因）。然而，那是在我的家人决定为今年的秘密圣诞老人添加新规则之前。我妈妈可能是某人的秘密圣诞老人，爸爸也可能是，但没有人可以成为他们的秘密圣诞老人（因为无论如何每个人每年都会收到礼物）。我弟媳妇的parents也算在内，我弟和他嫂子的parents.
不能配对当我输入这些新的限制规则时，我的测试大多失败，成功的很少（因为随机性通常会导致 2 或 1 个人在执行结束时没有秘密圣诞老人）。见下文：
Secret Santa 流程中的限制越多，要解决的问题就越复杂。我渴望提高这个项目的成功率。有办法吗？在考虑秘密圣诞老人限制时，我需要考虑哪些规则（排列的或数学上常见的）？
这是一个bipartite matching problem。您有两组节点：一组用于给予者，一组用于接收者。每组都有一个节点代表您家中的每个人。如果该对有效，则从提供者到接收者之间存在一条边。否则就没有边。然后应用二分匹配算法。