Date: 11/30/05 (Algorithms)    Keywords: php, database, shopping

So every year my friends and I do a Secret Santa exchange (the basic idea under a normal setup is to take a set of n names and derange them, so each person buys a gift for someone else, the 'secret' part being that nobody knows who's shopping for whom)... but we have a large group and there's some people who simply don't know each other, so being the programmer that I am, I scripted up a few PHP pages and a database to allow people to sign up to partipate, and then select the members that they would be willing to shop for. Ideally, I can call the "assignment" algorithm, write the results back to the database, and never know who has whom.

The trick now is to write an efficient (ideally! correctness is vital, no approximations! and n is not THAT large that exponential is out of the question) algorithm to find the shopping assignments OR prove that the input does not allow an assignment where every participant is: 1) being shopped for by exactly one person and 2) shops for exactly one person other than himself

Algorithmically speaking:

GIVEN:
D, a simple digraph (no loops), where a node is a person and an edge from X to Y indicates X is willing to shop for Y

FIND:
D', a subset of D, where forall v in V, indegree(v) = outdegree(v) = 1. D' need not be connected (there is no guarantee D is). OR prove that given D, there is no satisfying D'.

CONSTRAINTS:
Must be correct. Time is key. A large but reasonable amount of space may be used. Bonus points if the algorithm can be randomized (or even produces different output if you start at a different node, so long as other constraints are still met).


Since I have a small n, I can play around with insane solutions like "select a random assignment, check for validity, if not valid repeat"... but it seems like there should be some sort of algorithm to do this, but at the same time, I wonder if maybe it is more difficult than it seems...

Source: http://www.livejournal.com/community/algorithms/67335.html