Just over a year ago, someone asked me if Maple could help them pick names for their family gift exchange, because they were fed up with trying to find a solution by hand that met all their requirements. I knew it could be done, of course, and I spent some time (and at least one family dinner conversation) talking about how to do it. There wasn’t enough time to help my friend last year, but I dusted off my ideas, and my somewhat rusty Maple programming skills, and put something together for this year.

The problem, as stated to me, was “Assign everyone in the group the name of someone else in the group (the person they will buy a present for), with the restriction that no one can be assigned their partner.”

I decided to generalize a bit so that you can specify more than one person in the “do not pick” list for each individual, and the restrictions do not have to be reciprocal. That way, you can use it with rules like “parents cannot pick their children”, or “Elizabeth got Martin two years running, so she can’t pick him again this year”.

Ultimately I went with a “guess and check” approach. For each person, pick a name from the pool of suitable candidates (excluding themselves, anyone on their “do not pick” list, and anyone who has been picked already). Keep assigning names until either everyone has a name, or you end up in a situation where you can’t give someone a name. This can happen, for instance, if Todd is the last name, and the only unmatched name is Catherine, and Todd cannot pick Catherine. If that happens, I tossed all the names back into the virtual hat, gave it a good shake (i.e. randomize()) and tried again. Not as elegant as I would have liked, but it seemed like an effective approach.

It does feel like there ought to be a “nicer” solution. Maybe using graph theory? I know that my code will get into trouble if the restrictions are such that no solution exists.  If anyone has any ideas on other/better ways to solve this problem I’d be happy to hear them (now that I’ve had the fun of solving it myself first!).  

The application can be found on the application center: Gift Exchange Helper. The name picker algorithm is in the start-up code.

Happy gift giving!