This is a fun one; my stepmother walks in and says “I have a great idea! Why don’t you make a little app that randomly assigns people for secret santa!”
I think she was just trying to be nice; include my hobby in the a family tradition. She thought it sounded easy enough, and it shouldn’t take me more than 5 minutes. But let’s take a minute, and explore another case of “That should be easy, right?”
The Problem
For this who don’t know, Secret Santa is basically a game in which each person is assigned another random person to buy a gift for. In families or close groups, there is usually also the criteria that you can’t be assigned your partner. This seemingly inconsequential constraint transforms this problem from a simple nested for loop into something much more sinister: now, if we get unlucky and assign the wrong pairings, we can end up with an impossible problem.
The normal algorithm used by
- Write the names on to a bunch pieces of paper, one name per piece
- Put all the pieces into the hat
- Go in a circle and draw a name; if you get your partner, return it to the hat and draw again
A good computer scientist will look at this and glare menacingly at the last step; what happens if I draw my partner and there is no one left in the list? Usually you just announce it, and someone will trade with you.
I suppose you could do that in a computer program, but then you need to make sure you can get the person they are trading you, and that they can get the person you are trading them. This should be pretty straightforward if the only disallowed pairs are, well, pairings, but gets a smidgen more complicated if you say something like “You can’t be Secret Santa for someone within your family”.
The Actual Answer
The actual answer is to solve this as a constraint-satisfaction problem. This is a well known AI problem, and there are a ton of algorithms to solve it (for example, AC-3 https://en.wikipedia.org/wiki/AC-3_algorithm). But this might be a bit much to implement during thanksgiving day dinner.
The Engineers Answer
Attempt it; if we get an invalid pair, try again with random pairings. This should work 99% of the time, and if it gets stuck, just turn it off and back on again.
Guess which way I did it.