Proposal - Round Robin Gift Exchange

[jack]

Several people have suggested gift exhanges, or secret santas, or the like. The idea being, for people who don't know, that a group of people who would like to get each other presents, but don't have time, money or ideas enough, buy and receive one gift from people chosen randomly. (Normally by drawing names, so no-one occurs twice.)

I would use a computer algorithm, making the procedure:

* Sign up on a website listing 5-10 people you would buy a gift for one of.[1]

* You or it emails them and invites them to do the same.

* Next week, everyone is conveniently matched so they get an email giving them one person to buy a present for (ETA: from the list of people they specified they knew!), and will get one gift but they don't know who from yet.

* ETA: the matching may start from a friends list, but would probably need to be confirmed by hand.

I like the idea, and the tech necessary should be minimal.

Yes, I know a website that does that. (Comment with details.)
Jack should write one.
I'd do it.
Your algorithm isn't going to work because [comment].
Comments:

[1] Or more if you like, but there shouldn't be much point. And don't choose your best friends necessarily. Miss out anyone you're buying for anyway, and anyone you can't think of anything for. And choose randomly so no-one's offended.

Comments

[simont]

The code in question is in my puzzle collection: it's used in the puzzle "Tents", for which one of the criteria defining a correct solution is that the bipartite adjacency graph between tents and trees contains a perfect matching. (I think that's the single silliest winning condition in any puzzle I've ever seen. Most puzzles require at most linear-ish time to check a solution; finding perfect matchings is O(N³).)

So if you wander into the Subversion repository (a web interface to which is linked from the main puzzle page), you should find maxflow.h and maxflow.c which define a set of functions which use the Ford-Fulkerson algorithm to solve the max-flow/min-cut problem. This is a superset of the perfect matching problem, which is why I wrote that rather than a simpler matching-finder.

To solve a perfect matching problem, first construct a network containing one source, one node for each giver, one node for each recipient, and one sink. You need a graph edge going from the source to each giver, one from each recipient to the sink, and one going from each giver to each recipient iff that giver is willing to buy for that recipient. Hence, the maximum flow in that network is also the largest available matching. So then run the maxflow function; it will return you a flow array stating whether each graph edge is part of the matching. It will also return a total maximum-flow value telling you how many edges were in the matching, from which you can quickly tell whether it was complete or not. If not, you can examine the cut array to see which vertices were the cause of the problem: giver vertices with a 0 in the cut array are the too-selective set, and recipients with a 1 are the unlucky people who not enough givers will buy for.

An example of most of this code is given in the function new_game_desc() in tents.c, and again in the execute_move() function.

I hope that's of the slightest use :-)

[(Anonymous)]

Hopefully! It depends if anyone's interested, I'll look at the matching when I get there. But it's certainly more satisfying to reuse something than hack it by hand.