Well, it’s over: I got it out of my system.
I don’t even remember why, but I’d been thinking about trees lately (the comp-sci/data structure kind), and that slowly built into a mini-obsession. B-Trees, R-Trees, indexes, recursion… I found myself reading old programming books and Wikipedia articles until I was just about ready to go insane. In all of this, I was itching to find some little project to use them, and couldn’t come up with much more than “build one and look at it,” until I ran across the Wikipedia article for backtracking algorithms…
Enter the Christmas Gift Exchange.
Anne’s (large) family does a gift exchange every year, so that rather than everyone buying tons of stuff for everyone else, each person only buys presents for one other family member. (Kids are exempt, they still get tons of presents from everybody.) This keeps things more manageable, and more affordable for the givers, and it tends to make the gifts more meaningful too. Gift givers get their people assigned randomly, and who you’re buying for is supposed to be kept a secret until the exchange at the Christmas party.
The usual selection process happens after Thanksgiving dinner, when Anne and her sisters put everyone’s name in a hat, and someone pulls names to match against the list of participants. So far so good and pretty random, but there are other considerations: spouses maybe shouldn’t buy for each other, ditto parents and children, or someone ends up buying for the same person several years in a row — the “selection committee” would re-do a selection if the original draw seemed really unacceptable. Then we all get our slips of paper and start our shopping.
I end up thinking off and on (usually just after Thanksgiving),that this rigamarole could and maybe should be automated, especially in light of the need to keep things random while also avoiding unacceptable giver/receiver combinations. I thought of a few ways that it could be done, and eventually started thinking of this as a problem in graph theory, where each participant could be considered a node in the graph, and each possible gift exchange would be an edge connecting between giver and receiver. Then maybe the problem could be looked at as a problem in traversing the graph, and the solution might look something like Dijkstra’s Algorithm. That was all well and good, but I don’t know enough graph theory to even be dangerous.
But thinking in those terms made the problem look like it could be handled with tree structures and some kind of recursion, and when I happened across that Wikipedia article something clicked. Hmmmm…
I wrote a python script to hold some data structures (mostly dictionaries of name lists); once I got that down, the rest came pretty easy: how to add constraints , how to recurse through the backtracking algorithm, etc. I added a few bells and whistles and, surprisingly, the whole thing worked like a charm.
The most ironic thing about the project is that my results were originally the full set of all possible solutions, saved in a tree structure as nested lists, but once I got the tree obsession out of my system I abandoned that to just return the first randomly selected solution.
(Actually, that’s not the most ironic part. The most ironic thing about this is that it will never be used — the selection “rigamarole,” as I called it, is actually a fun and much-anticipated part of the holiday rituals.)
