Last year, we published the source code we used to draw names out of our virtual hat to decide who would be giving a gift to whom as part of our annual t-shirt exchange tradition. However, a quick glance at that old code reveals its problems:
1. It’s inefficient. It uses brute force to match a set of givers to a set of recipients, then it checks to see that no one was assigned to give a gift to themselves. This works OK for small sets, but for larger sets it is very inefficient.
2. It creates the potential that two people will exchange gifts with each other. This is not a bad thing in and of itself; it’s just that if you think about the entire set in terms of a graph, the graph has the potential to lose connectivity. In larger sets, you may have many subsets of gift exchangers without any connectivity between each group. This would be particularly bad if you were trying to create the world’s largest gift exchange, as reddit is attempting to do this year with its Secret Santa program; it would be a shame if you were trying to break the record only to discover that rather than one humongous group exchanging gifts, you had 2 or 3 unconnected groups exchanging gifts. Something like that in a small group would look like the following:
Ideally, we’d prefer to have something like this (a directed cycle graph):
Fortunately, something like this in programming is easy—much easier than what what we tried to do last year. (In my defense, I did write last year’s script in a few minutes without thinking about it much.)
To represent a directed cycle graph as a data structure, you can use a circularly linked list. For the very simple code implementation below, I’m going to use a shuffled array and iterate through it once. For the last node, I’m going to use a stored reference to the first node to complete the circle. However, for more advanced programs, you would probably use a modified version of SplDoublyLinkedList where nextNode for the last node always returns the first node (and prevNode for the first node always returns the last node).
<?php
$emails = array(
'name1@yourcompany.com',
'name2@yourcompany.com',
'name3@yourcompany.com',
'name4@yourcompany.com',
'name5@yourcompany.com',
);
// shuffle the emails
shuffle($emails);
// grab the first person
$giver = $first_person = array_shift($emails);
while (null != ($givee = array_shift($emails))) {
give($giver, $givee);
// now the givee becomes the giver
$giver = $givee;
}
// once we reach this point, the final givee is the first person
give($giver, $first_person);
function give($giver, $givee) {
echo(sprintf('%s gives to %s', $giver, $givee));
}
?>
See, much simpler than last years. Happy holidays, folks!
