Adam Monsen

Every year my family does a gift exchange. Names are chosen out of a hat to randomly assign pairs. Certain rules are followed:

1. give to a different person than last year
2. partners can’t be nuclear family members (or bf/gf/so/etc.)
3. can’t choose yourself
4. participants give one gift only
5. participants receive one gift only

I decided to give it the old college try in Python. Drawing names following the rules certainly posed more of a challenge than I anticipated! But I think I figured it out. At least, I figured out the “lazy programmer” way to solve it, not the statistician/np-complete/combinatorial/elegant mathy way to solve it.

This script can be used to “draw names” for a Christmas gift exchange.

It’s very brute-force, and works differently than a real-life drawing (what the Pierce fam currently does) in the following ways:

• instead of every giver drawing from a hat containing every un-paired participant, that “hat” only contains valid recipients (based on the above rules)
• when it’s down to the last couple of people, but they can’t give to each other, all matches so far are scrapped and the whole process starts anew (same if we end up with 0 recipients and 1 giver) — a more real-world scenario might be to simply break an existing pair and re-draw for just a few people

Runtime for the full draw is generally under .03 seconds. Here’s an example run for 2010:

$ ./gift_exchange.py
Amika gives to Jim
D.J. gives to Jose
Grandma gives to Ruby
Grandpa gives to Suzy
Jim gives to Grandma
Jose gives to D.J.
Ruby gives to Grandpa
Suzy gives to Amika

I didn’t do extensive testing, just ran it 10 million times or so and watched to see that it didn’t crash or hang.

Feedback/bug reports/patches/forks welcome!