Secret Santa Selection 

Every year my extended family does a "secret santa" gift exchange.  Each person draws another person at random and then gets a gift for them. At first, none of my siblings were married, and so the draw was completely random. Then, as people got married, we added the restriction that spouses should not draw each others names.  This restriction meant that we moved from using slips of paper on a hat to using a simple computer program to choose names.  Then people began to complain when they would get the same person two years in a row, so the program was modified to keep some history and avoid given anyone a name in their recent history.  This year, not everyone was participating, and so after removing names, and limiting the number of exclusions to four per person, I had data something like this: 

This data can be stored as a nested list of strings for Maple: 

(1)

	(2)

The very simple program I used is something like this the one below.  It just simulates drawing names out of a hat and throwing away the whole draw and starting again if the restrictions are not met. When I ran it this year, I had to stop it after 10 minutes with no output (the code below stops after unsuccessfully trying random draws). 

Randomly Search For Match

Since it is completely random, I did not know for sure that there was no acceptable match, and that the program was just very unlucky. 

Maybe it would have been smarter to simulate drawing names one at a time and redrawing each until an acceptable name was found and only starting over if no acceptable matches remained.  This program does not find a match either but it is still random, so it could also be getting very unlucky and missing a possible match.
 

Randomly Match Each Name

Now, it would be possible to write and program to enumerate all possible matches, and if that collection were not empty, randomly choose a match.  But, instead, I applied the GraphTheory package to the problem. 

A standard approach for this sort of thing is to create a bipartite graph with each person listed twice (once as a gifter once as giftee) with an edge representing each possible match.  The following one line call builds such a graph using the first three letters of each name to label its gifter node and the same appended with a "2" for its gifter node. 

(3)

Just looking at the graph, it is not obvious that there are no matches:
 

Fortunately, there is a command to search for the largest possible matching in a bipartite graph.
 

(4)

The 7 in the output means that the largest matching in the graph is 7 edges.  Since we have 8 people, that means it is not possible to match the people given the restrictions!

You can draw the matching, and see that it is, indeed, not full.  Mia is not a giftee and Ryan is not a gifter. 

In this case, you can better see why it is not possible to generate a match by breaking the graph into its connected components.
 

(5)

(6)

(7)

The graph can split into two pieces: one with 4 gifters and 5 giftees and the other with 4 gifters and 3 giftees.  When arranged this way, it is absolutely clear that there can be no match.  Fortunately, Mia was very bad this year, and Ryan is sort on cash, so this matching worked out just fine.