Python Secret Santa Gift Exchange: Optimize Matches with pyge
By Seth Black Updated September 27, 2024
As is true with many families, when my wife and I got engaged we were both immediately thrust into each other's family gift exchanges; with my wife being put in charge of the Secret Santa gift exchange. Because she knows all about my background in math and computer science my wife has made some quite lofty demands for a piece of software that would replace the hat containing folded pieces of paper with hand-written names. Python Gift Exchange Picker (or better, pyge and pronounced like the Pidgey from Pokémon) is my third and best implementation of my wife's requirements:
- It must match each person to a different person.
- The match should not be in the same household.
- The match should not be the same gender.
- The match should not be in the same age group.
- The match must not happen again for at least three years.
To accomplish this, pyge first needs a list of participants along with their associated "social attributes" or, feature sets. I will be providing example code snippets as I go along. These snippets are not exact representations of what's in the code (which you can see on github) they are more shown to explain my thought process.
participants = [ {'name': 'Mom', 'generation': 'boomer', 'sex': 'F', 'household': 'mom and dad',}, {'name': 'Dad', 'generation': 'boomer', 'sex': 'M', 'household': 'mom and dad',}, {'name': 'Brother', 'generation': 'millennial', 'sex': 'F', 'household': 'brother',}, {'name': 'Sister', 'generation': 'millennial', 'sex': 'M', 'household': 'sister and brother in law',}, {'name': 'Me', 'generation': 'beteen gen x and millennial', 'sex': 'M', 'household': 'us',}, {'name': 'Wife', 'generation': 'beteen gen x and millennial', 'sex': 'F', 'household': 'us',}, ]
It then transforms each participant's feature set into floating point numerical values.
participants = [ {'name': 'Mom', 'generation': 0., 'sex': 0., 'household': 0.,}, {'name': 'Dad', 'generation': 0., 'sex': 1., 'household': 0.,}, {'name': 'Brother', 'generation': 1., 'sex': 0., 'household': 1,}, {'name': 'Sister', 'generation': 1., 'sex': 1., 'household': 2.}, {'name': 'Me', 'generation': 2., 'sex': 1., 'household': 3.}, {'name': 'Wife', 'generation': 2., 'sex': 0., 'household': 3.}, ]
Each value is then vectorized and a pairwise euclidean distance between each participant is computed; this can be represented as either a graph or a matrix - I chose a matrix.
| Mom | Dad | Brother | Sister | Me | Wife | |
| Mom | - | 0.53 | 1.40 | 0.89 | 1.10 | 0.46 |
| Dad | 0.53 | - | 0.89 | 1.40 | 0.46 | 1.10 |
| Brother | 1.49 | 0.89 | - | 0.26 | 0.68 | 0.72 |
| Sister | 0.89 | 1.40 | 0.26 | - | 0.72 | 0.68 |
| Me | 1.10 | 0.46 | 0.72 | 0.68 | - | 0.53 |
| Wife | 0.46 | 1.10 | 0.72 | 0.68 | 0.53 | - |
participants = [ {'name': 'Mom', distances: ['Dad': 0.53, 'Brother': 1.4, 'Sister': 0.89, 'Me': 1.1, 'Wife': 0.46], {'name': 'Dad', distances: ['Mom': 0.53, 'Brother': 0.89, 'Sister': 1.4, 'Me': 0.46, 'Wife': 1.1], {'name': 'Brother', distances: ['Dad': 0.89, 'Mom': 1.4., 'Sister': 0.26, 'Me': 0.68, 'Wife': 0.72], {'name': 'Sister', distances: ['Dad': 1.4, 'Brother': 0.26, 'Mom': 0.89., 'Me': 0.72, 'Wife': 0.68], {'name': 'Me', distances: ['Dad': 0.46, 'Brother': 0.72, 'Sister': 0.68, 'Mom': 1.1., 'Wife': 0.53], {'name': 'Wife', distances: ['Dad': 1.1, 'Brother': 0.68, 'Sister': 0.72, 'Me': 0.53, 'Mom': 0.46], ]
The distances are then multiplied by a per-participant "qualifier" coefficient. The qualifier coefficient is either 0.0 or 1.0 and is used to disqualify participants who were paired in previous years. For this example we'll pretend that the following pairings were last year's: Mom & Me, Dad & Wife, Brother & Dad, Sister & Mom, Me & Sister, Wife & Brother
| Mom | Dad | Brother | Sister | Me | Wife | |
| Mom | - | 0.53 | 1.40 | 0.89 | 0.00 | 0.46 |
| Dad | 0.53 | - | 0.89 | 1.40 | 0.46 | 0.00 |
| Brother | 1.49 | 0.00 | - | 0.26 | 0.68 | 0.72 |
| Sister | 0.00 | 1.40 | 0.26 | - | 0.72 | 0.68 |
| Me | 1.10 | 0.46 | 0.72 | 0.00 | - | 0.53 |
| Wife | 0.46 | 1.10 | 0.00 | 0.68 | 0.53 | - |
participants = [ {'name': 'Mom', distances: ['Dad': 0.53, 'Brother': 1.4, 'Sister': 0.89, 'Me': 0.0, 'Wife': 0.46], {'name': 'Dad', distances: ['Mom': 0.53, 'Brother': 0.89, 'Sister': 1.4, 'Me': 0.46, 'Wife': 0.0], {'name': 'Brother', distances: ['Dad': 0.0, 'Mom': 1.4., 'Sister': 0.26, 'Me': 0.68, 'Wife': 0.72], {'name': 'Sister', distances: ['Dad': 1.4, 'Brother': 0.26, 'Mom': 0.0., 'Me': 0.72, 'Wife': 0.68], {'name': 'Me', distances: ['Dad': 0.46, 'Brother': 0.72, 'Sister': 0.0, 'Mom': 1.1., 'Wife': 0.53], {'name': 'Wife', distances: ['Dad': 1.1, 'Brother': 0.0, 'Sister': 0.72, 'Me': 0.53, 'Mom': 0.46], ]
The participants are then iterated over and randomly matched using a weighted distribution. The following table shows the likelihood of participant matches.
| Mom | Dad | Brother | Sister | Me | Wife | |
| Mom | - | 16.2% | 42.7% | 27.1% | 0.0% | 14.0% |
| Dad | 16.2% | - | 27.1% | 42.7% | 14.0% | 0.0% |
| Brother | 47.3% | 0.0% | - | 8.3% | 21.6% | 22.9% |
| Sister | 0.0% | 45.8% | 8.5% | - | 23.5% | 22.2% |
| Me | 39.1% | 16.4% | 25.6% | 0.0% | - | 18.9% |
| Wife | 16.6% | 39.7% | 0.0% | 24.5% | 19.1% | - |
This matrix can be used to generate a list of pairings. Woo!
Mom & Brother
Dad & Sister
Brother & Wife
Sister & Me
Me & Mom
Wife & Dad
Finally, if no matches can be made and there are still participants pyge will backtrack until all participants can be successfully matched or it is discovered that it is impossible to match the given set of participants. In that case, we'll need to add more family members!
