Secret Santa is a graph traversal problem by Tristan Mahr.
From the post:
Last week at Thanksgiving, my family drew names from a hat for our annual game of Secret Santa. Actually, it wasn’t a hat but you know what I mean. (Now that I think about it, I don’t think I’ve ever seen names drawn from a literal hat before!) In our family, the rules of Secret Santa are pretty simple:
- The players’ names are put in “a hat”.
- Players randomly draw a name from a hat, become that person’s Secret Santa, and get them a gift.
- If a player draws their own name, they draw again.
Once again this year, somebody asked if we could just use an app or a website to handle the drawing for Secret Santa. Or I could write a script to do it I thought to myself. The problem nagged at the back of my mind for the past few days. You could just shuffle the names… no, no, no. It’s trickier than that.
In this post, I describe a couple of algorithms for Secret Santa sampling using R and directed graphs. I use the DiagrammeR package which creates graphs from dataframes of nodes and edges, and I liberally use dplyr verbs to manipulate tables of edges.
If you would like a more practical way to use R for Secret Santa, including automating the process of drawing names and emailing players, see this blog post.
…
If you haven’t done your family Secret Santa yet, you are almost late! (November 30, 2017)
Enjoy!