<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/secret-santa-is-a-graph-traversal-problem/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://tjmahr.github.io/secret-santa-graph-traversal/"> Higher Order Functions</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Last week at Thanksgiving, my family drew names from a hat for our annual game<br>
of Secret Santa. Actually, it wasn’t a hat but you know what I mean. (Now that I<br>
think about it, I don’t think I’ve ever seen names drawn from a literal hat<br>
before!) In our family, the rules of Secret Santa are pretty simple:</p>
<ul>
<li>The players’ names are put in “a hat”.</li>
<li>Players randomly draw a name from a hat, become that person’s Secret Santa,<br>
and get them a gift.</li>
<li>If a player draws their own name, they draw again.</li>
</ul>
<p>Once again this year, somebody asked if we could just use an app or a website to<br>
handle the drawing for Secret Santa. <em>Or I could write a script to do it</em> I<br>
thought to myself. The problem nagged at the back of my mind for the past few<br>
days. <em>You could just shuffle the names… no, no, no. It’s trickier than that.</em></p>
<p>In this post, I describe a couple of algorithms for Secret Santa sampling using<br>
R and directed graphs. I use the<br>
<a rel="nofollow" href="https://github.com/rich-iannone/DiagrammeR" target="_blank">DiagrammeR package</a> which creates<br>
graphs from dataframes of nodes and edges, and I liberally use<br>
<a rel="nofollow" href="http://r4ds.had.co.nz/transform.html" target="_blank">dplyr verbs</a> to manipulate tables of<br>
edges.</p>
<p>If you would like a more practical way to use R for Secret Santa, including<br>
automating the process of drawing names and <em>emailing players</em>, see<br>
<a rel="nofollow" href="http://livefreeordichotomize.com/2017/11/15/secret-sampling/" target="_blank">this blog post</a>.</p>
<h2>Making a graph, connecting nodes twice</h2>
<p>Let’s start with a subset of my family’s game of just five players. I assign<br>
each name a unique ID number.</p>
<div>
<div>
<pre><code><span>library</span><span>(</span><span>DiagrammeR</span><span>)</span><span>
</span><span>library</span><span>(</span><span>magrittr</span><span>)</span><span>
</span><span>library</span><span>(</span><span>dplyr</span><span>,</span><span> </span><span>warn.conflicts</span><span> </span><span>=</span><span> </span><span>FALSE</span><span>)</span><span>
</span><span>players</span><span> </span><span>&lt;-</span><span> </span><span>tibble</span><span>::</span><span>tribble</span><span>(</span><span>
</span><span>~</span><span> </span><span>Name</span><span>,</span><span> </span><span>~</span><span> </span><span>Number</span><span>,</span><span>
</span><span>&quot;Jeremy&quot;</span><span>,</span><span> </span><span>1</span><span>,</span><span>
</span><span>&quot;TJ&quot;</span><span>,</span><span> </span><span>2</span><span>,</span><span> </span><span>&quot;Jonathan&quot;</span><span>,</span><span> </span><span>3</span><span>,</span><span> </span><span>&quot;Alex&quot;</span><span>,</span><span> </span><span>4</span><span>,</span><span> </span><span>&quot;Marissa&quot;</span><span>,</span><span> </span><span>5</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p>We can think of the players as nodes in a directed graph. An edge connecting two<br>
players indicates a “gives-to” (Secret Santa) relationship. Suppose I drew<br>
Marissa’s name. Then the graph will have an edge connecting me to her. In the<br>
code below, I use DiagrammeR to create a graph by combining a node dataframe<br>
(<code>create_node_df()</code>) and an edge dataframe (<code>create_edge_df()</code>).</p>
<div>
<div>
<pre><code><span>nodes</span><span> </span><span>&lt;-</span><span> </span><span>create_node_df</span><span>(</span><span>
</span><span>n</span><span> </span><span>=</span><span> </span><span>nrow</span><span>(</span><span>players</span><span>),</span><span>
</span><span>type</span><span> </span><span>=</span><span> </span><span>players</span><span>$</span><span>Name</span><span>,</span><span>
</span><span>label</span><span> </span><span>=</span><span> </span><span>players</span><span>$</span><span>Name</span><span>)</span><span>
</span><span>tj_drew_marissa</span><span> </span><span>&lt;-</span><span> </span><span>create_edge_df</span><span>(</span><span>
</span><span>from</span><span> </span><span>=</span><span> </span><span>2</span><span>,</span><span> </span><span>to</span><span> </span><span>=</span><span> </span><span>5</span><span>,</span><span> </span><span>rel</span><span> </span><span>=</span><span> </span><span>&quot;gives-to&quot;</span><span>,</span><span>
</span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#FF4136&quot;</span><span>,</span><span>
</span><span>penwidth</span><span> </span><span>=</span><span> </span><span>1</span><span>)</span><span>
</span><span>create_graph</span><span>(</span><span>nodes</span><span>,</span><span> </span><span>tj_drew_marissa</span><span>)</span><span> </span><span>%>%</span><span> </span><span>render_graph</span><span>()</span><span>
</span></code></pre>
</div>
</div>
<p><br>
<br>
</p>
<p>Before the game starts, anyone could draw anyone else’s name, so let’s visualize<br>
all possible gives-to relations. We can do this by using <code>combn(n, 2)</code> to<br>
generate all n-choose-2 pairs and creating two edges for each pair.</p>
<div>
<div>
<pre><code><span>combn</span><span>(</span><span>players</span><span>$</span><span>Name</span><span>,</span><span> </span><span>2</span><span>)</span><span>
</span><span>#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] </span><span>
</span><span>#> [1,] &quot;Jeremy&quot; &quot;Jeremy&quot; &quot;Jeremy&quot; &quot;Jeremy&quot; &quot;TJ&quot; &quot;TJ&quot; &quot;TJ&quot; </span><span>
</span><span>#> [2,] &quot;TJ&quot; &quot;Jonathan&quot; &quot;Alex&quot; &quot;Marissa&quot; &quot;Jonathan&quot; &quot;Alex&quot; &quot;Marissa&quot;</span><span>
</span><span>#> [,8] [,9] [,10] </span><span>
</span><span>#> [1,] &quot;Jonathan&quot; &quot;Jonathan&quot; &quot;Alex&quot; </span><span>
</span><span>#> [2,] &quot;Alex&quot; &quot;Marissa&quot; &quot;Marissa&quot;</span><span>
</span><span># All the edge-manipulating functions in this post take an optional take `...`</span><span>
</span><span># argument for setting the style of edges.</span><span>
</span><span>create_all_giving_edges</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>xs</span><span>,</span><span> </span><span>...</span><span>)</span><span> </span><span>{</span><span>
</span><span>aes_options</span><span> </span><span>&lt;-</span><span> </span><span>quos</span><span>(</span><span>...</span><span>)</span><span>
</span><span>pairs</span><span> </span><span>&lt;-</span><span> </span><span>combn</span><span>(</span><span>seq_along</span><span>(</span><span>xs</span><span>),</span><span> </span><span>2</span><span>)</span><span>
</span><span># Each column from `combn()` is a pair. We make an edge moving down the column</span><span>
</span><span># and another edge up the column by having each row as a `from` index and a</span><span>
</span><span># `to` index.</span><span>
</span><span>from</span><span> </span><span>&lt;-</span><span> </span><span>c</span><span>(</span><span>pairs</span><span>[</span><span>1</span><span>,</span><span> </span><span>],</span><span> </span><span>pairs</span><span>[</span><span>2</span><span>,</span><span> </span><span>])</span><span>
</span><span>to</span><span> </span><span>&lt;-</span><span> </span><span>c</span><span>(</span><span>pairs</span><span>[</span><span>2</span><span>,</span><span> </span><span>],</span><span> </span><span>pairs</span><span>[</span><span>1</span><span>,</span><span> </span><span>])</span><span>
</span><span>create_edge_df</span><span>(</span><span>from</span><span> </span><span>=</span><span> </span><span>from</span><span>,</span><span> </span><span>to</span><span> </span><span>=</span><span> </span><span>to</span><span>)</span><span> </span><span>%>%</span><span> </span><span>mutate</span><span>(</span><span>!!!</span><span> </span><span>aes_options</span><span>)</span><span> </span><span>%>%</span><span> </span><span>as_tibble</span><span>()</span><span>
</span><span>}</span><span>
</span><span>all_possible_edges</span><span> </span><span>&lt;-</span><span> </span><span>create_all_giving_edges</span><span>(</span><span>
</span><span>players</span><span>$</span><span>Name</span><span>,</span><span> </span><span>rel</span><span> </span><span>=</span><span> </span><span>&quot;potential-gift&quot;</span><span>,</span><span> </span><span>penwidth</span><span> </span><span>=</span><span> </span><span>.5</span><span>,</span><span>
</span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#CCCCCC90&quot;</span><span>)</span><span>
</span><span>create_graph</span><span>(</span><span>nodes</span><span>,</span><span> </span><span>all_possible_edges</span><span>)</span><span> </span><span>%>%</span><span> </span><span>render_graph</span><span>()</span><span>
</span></code></pre>
</div>
</div>
<p><br>
<br>
</p>
<h3>A fast, simple solution is a Hamiltonian path</h3>
<p>Do you need to organize a gift-giving drawing for a group of people? The easiest<br>
solution is to shuffle the names and have the first name give to the second name,<br>
the second to the third, and so on with last name giving looping back around to<br>
the first name. This solution is equivalent to walking through the graph and<br>
visiting every node just once. Such a path is called a<br>
<a rel="nofollow" href="https://en.wikipedia.org/wiki/Hamiltonian_path" target="_blank">Hamiltonian path</a>.</p>
<p>Here we find a Hamiltonian path and create a helper function <code>overwrite_edges()</code><br>
to update the edges that fall on the path.</p>
<div>
<div>
<pre><code><span>overwrite_edges</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>old_df</span><span>,</span><span> </span><span>new_df</span><span>)</span><span> </span><span>{</span><span>
</span><span>old_df</span><span> </span><span>%>%</span><span>
</span><span>anti_join</span><span>(</span><span>new_df</span><span>,</span><span> </span><span>by</span><span> </span><span>=</span><span> </span><span>c</span><span>(</span><span>&quot;from&quot;</span><span>,</span><span> </span><span>&quot;to&quot;</span><span>))</span><span> </span><span>%>%</span><span>
</span><span>bind_rows</span><span>(</span><span>new_df</span><span>)</span><span>
</span><span>}</span><span>
</span><span>create_hamiltonian_gift_edges</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>xs</span><span>,</span><span> </span><span>...</span><span>)</span><span> </span><span>{</span><span>
</span><span>loop_from</span><span> </span><span>&lt;-</span><span> </span><span>sample</span><span>(</span><span>seq_along</span><span>(</span><span>xs</span><span>))</span><span>
</span><span># last name gives to first</span><span>
</span><span>loop_to</span><span> </span><span>&lt;-</span><span> </span><span>c</span><span>(</span><span>loop_from</span><span>[</span><span>-1</span><span>],</span><span> </span><span>loop_from</span><span>[</span><span>1</span><span>])</span><span>
</span><span>create_edge_df</span><span>(</span><span>from</span><span> </span><span>=</span><span> </span><span>loop_from</span><span>,</span><span> </span><span>to</span><span> </span><span>=</span><span> </span><span>loop_to</span><span>,</span><span> </span><span>...</span><span>)</span><span>
</span><span>}</span><span>
</span><span># For reproducible blogging</span><span>
</span><span>set.seed</span><span>(</span><span>11282017</span><span>)</span><span>
</span><span>hamiltonian_edges</span><span> </span><span>&lt;-</span><span> </span><span>create_hamiltonian_gift_edges</span><span>(</span><span>
</span><span>players</span><span>$</span><span>Name</span><span>,</span><span>
</span><span>rel</span><span> </span><span>=</span><span> </span><span>&quot;gives-to&quot;</span><span>,</span><span>
</span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#FF4136&quot;</span><span>,</span><span>
</span><span>penwidth</span><span> </span><span>=</span><span> </span><span>1</span><span>
</span><span>)</span><span>
</span><span>all_possible_edges</span><span> </span><span>%>%</span><span> </span><span>overwrite_edges</span><span>(</span><span>hamiltonian_edges</span><span>)</span><span> </span><span>%>%</span><span> </span><span>create_graph</span><span>(</span><span>nodes</span><span>,</span><span> </span><span>.</span><span>)</span><span> </span><span>%>%</span><span> </span><span>render_graph</span><span>()</span><span>
</span></code></pre>
</div>
</div>
<p><br>
<br>
</p>
<p>As promised, the red paths loop through all nodes exactly once. No one is their<br>
own gift giver :white_check_mark:, and everyone has an incoming red path<br>
:white_check_mark: and an outgoing red path :white_check_mark:. Very nice.<br>
<em>Actually</em>… let’s put that checklist into a validation function.</p>
<div>
<div>
<pre><code><span># Check for valid gift-giving edges</span><span>
</span><span>has_valid_gift_edges</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>edge_df</span><span>,</span><span> </span><span>indices</span><span>)</span><span> </span><span>{</span><span>
</span><span>indices</span><span> </span><span>&lt;-</span><span> </span><span>sort</span><span>(</span><span>unique</span><span>(</span><span>indices</span><span>))</span><span>
</span><span>pairs</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span> </span><span>%>%</span><span> </span><span>filter</span><span>(</span><span>rel</span><span> </span><span>==</span><span> </span><span>&quot;gives-to&quot;</span><span>)</span><span>
</span><span>no_self_loop</span><span> </span><span>&lt;-</span><span> </span><span>!</span><span>any</span><span>(</span><span>pairs</span><span>$</span><span>from</span><span> </span><span>==</span><span> </span><span>pairs</span><span>$</span><span>to</span><span>)</span><span>
</span><span>exhaustive_from</span><span> </span><span>&lt;-</span><span> </span><span>isTRUE</span><span>(</span><span>all.equal</span><span>(</span><span>sort</span><span>(</span><span>pairs</span><span>$</span><span>from</span><span>),</span><span> </span><span>indices</span><span>))</span><span>
</span><span>exhaustive_to</span><span> </span><span>&lt;-</span><span> </span><span>isTRUE</span><span>(</span><span>all.equal</span><span>(</span><span>sort</span><span>(</span><span>pairs</span><span>$</span><span>to</span><span>),</span><span> </span><span>indices</span><span>))</span><span>
</span><span>all</span><span>(</span><span>no_self_loop</span><span>,</span><span> </span><span>exhaustive_from</span><span>,</span><span> </span><span>exhaustive_to</span><span>)</span><span>
</span><span>}</span><span>
</span><span>has_valid_gift_edges</span><span>(</span><span>hamiltonian_edges</span><span>,</span><span> </span><span>all_possible_edges</span><span>$</span><span>from</span><span>)</span><span>
</span><span>#> [1] TRUE</span><span>
</span></code></pre>
</div>
</div>
<p>Despite its elegance, this solution does not simulate drawing names from a<br>
hat! Because each node is visited only once, there is no backtracking, so there<br>
there is no reciprocal gift-giving or other sub-circuits in the graph.</p>
<p>Whether you think this is a bad thing is a matter of preference. Personally, I<br>
would like all remaining pairs to be equally probable at each step of the<br>
drawing. This is not the case when backtracking is not allowed. (For example, if<br>
I draw Marissa, then all of the remaining edges are not equally likely because<br>
P(Marissa draws TJ | TJ draws Marissa) = 0.)</p>
<h2>Okay, do the hat-drawing thing already</h2>
<p>Let’s think about what happens when I draw Marissa’s name from a nice big red<br>
Santa hat.</p>
<ul>
<li>The edge from TJ to Marissa is fixed. (I drew her name.)</li>
<li>All other edges from TJ become illegal. (I can’t draw any more names.)</li>
<li>All other edges onto Marissa become illegal. (No one else can draw her name<br>
either.)</li>
</ul>
<p>To simulate a single hat-drawing, we randomly select a legal edge, fix it, and<br>
delete all illegal edges. Let’s work through a couple of examples.</p>
<p>First, we need some helper functions.</p>
<div>
<div>
<pre><code><span>draw_secret_santa_edge</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>edge_df</span><span>,</span><span> </span><span>...</span><span>)</span><span> </span><span>{</span><span>
</span><span>aes_options</span><span> </span><span>&lt;-</span><span> </span><span>quos</span><span>(</span><span>...</span><span>)</span><span>
</span><span>edge_df</span><span> </span><span>%>%</span><span>
</span><span>filter</span><span>(</span><span>rel</span><span> </span><span>!=</span><span> </span><span>&quot;gives-to&quot;</span><span>)</span><span> </span><span>%>%</span><span>
</span><span>sample_n</span><span>(</span><span>1</span><span>)</span><span> </span><span>%>%</span><span>
</span><span>mutate</span><span>(</span><span>!!!</span><span> </span><span>aes_options</span><span>)</span><span>
</span><span>}</span><span>
</span><span>find_illegal_edges</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>edge_df</span><span>,</span><span> </span><span>edge</span><span>,</span><span> </span><span>...</span><span>)</span><span> </span><span>{</span><span>
</span><span>aes_options</span><span> </span><span>&lt;-</span><span> </span><span>quos</span><span>(</span><span>...</span><span>)</span><span>
</span><span>outgoing</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span> </span><span>%>%</span><span>
</span><span>filter</span><span>(</span><span>from</span><span> </span><span>%in%</span><span> </span><span>edge</span><span>$</span><span>from</span><span>)</span><span>
</span><span>incoming</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span> </span><span>%>%</span><span>
</span><span>filter</span><span>(</span><span>to</span><span> </span><span>%in%</span><span> </span><span>edge</span><span>$</span><span>to</span><span>)</span><span>
</span><span># The one edge that is not illegal is in both </span><span>
</span><span># the incoming and outgoing sets</span><span>
</span><span>to_keep</span><span> </span><span>&lt;-</span><span> </span><span>dplyr</span><span>::</span><span>intersect</span><span>(</span><span>outgoing</span><span>,</span><span> </span><span>incoming</span><span>)</span><span>
</span><span>outgoing</span><span> </span><span>%>%</span><span> </span><span>bind_rows</span><span>(</span><span>incoming</span><span>)</span><span> </span><span>%>%</span><span> </span><span>anti_join</span><span>(</span><span>to_keep</span><span>,</span><span> </span><span>by</span><span> </span><span>=</span><span> </span><span>c</span><span>(</span><span>&quot;from&quot;</span><span>,</span><span> </span><span>&quot;to&quot;</span><span>))</span><span> </span><span>%>%</span><span> </span><span>mutate</span><span>(</span><span>!!!</span><span> </span><span>aes_options</span><span>)</span><span>
</span><span>}</span><span>
</span></code></pre>
</div>
</div>
<p>Here we draw a single edge (red with fat arrow). All of the other edges that<br>
point to the same node are illegal (navy) as are all of the edges that have the<br>
same origin as the drawn edge.</p>
<div>
<div>
<pre><code><span>current_pick</span><span> </span><span>&lt;-</span><span> </span><span>draw_secret_santa_edge</span><span>(</span><span>
</span><span>all_possible_edges</span><span>,</span><span>
</span><span>rel</span><span> </span><span>=</span><span> </span><span>&quot;gives-to&quot;</span><span>,</span><span> </span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#FF4136&quot;</span><span>,</span><span> </span><span>penwidth</span><span> </span><span>=</span><span> </span><span>1</span><span>,</span><span> </span><span>arrowsize</span><span> </span><span>=</span><span> </span><span>1</span><span>)</span><span>
</span><span>current_illegal_edges</span><span> </span><span>&lt;-</span><span> </span><span>all_possible_edges</span><span> </span><span>%>%</span><span>
</span><span>find_illegal_edges</span><span>(</span><span>current_pick</span><span>,</span><span> </span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#001f3f&quot;</span><span>,</span><span> </span><span>penwidth</span><span> </span><span>=</span><span> </span><span>.5</span><span>)</span><span>
</span><span>all_possible_edges</span><span> </span><span>%>%</span><span>
</span><span>overwrite_edges</span><span>(</span><span>current_pick</span><span>)</span><span> </span><span>%>%</span><span> </span><span>overwrite_edges</span><span>(</span><span>current_illegal_edges</span><span>)</span><span> </span><span>%>%</span><span> </span><span>create_graph</span><span>(</span><span>nodes</span><span>,</span><span> </span><span>.</span><span>)</span><span> </span><span>%>%</span><span> </span><span>render_graph</span><span>(</span><span>title</span><span> </span><span>=</span><span> </span><span>&quot;Selected vs. illegal&quot;</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p><br>
<br>
</p>
<p>We delete those illegal edges and leaving us with the following graph.</p>
<div>
<div>
<pre><code><span>edges_after_pick1</span><span> </span><span>&lt;-</span><span> </span><span>all_possible_edges</span><span> </span><span>%>%</span><span>
</span><span>overwrite_edges</span><span>(</span><span>current_pick</span><span> </span><span>%>%</span><span> </span><span>mutate</span><span>(</span><span>arrowsize</span><span> </span><span>=</span><span> </span><span>NULL</span><span>))</span><span> </span><span>%>%</span><span> </span><span>anti_join</span><span>(</span><span>current_illegal_edges</span><span>,</span><span> </span><span>by</span><span> </span><span>=</span><span> </span><span>&quot;id&quot;</span><span>)</span><span> </span><span>create_graph</span><span>(</span><span>nodes</span><span>,</span><span> </span><span>edges_after_pick1</span><span>)</span><span> </span><span>%>%</span><span> </span><span>render_graph</span><span>(</span><span>title</span><span> </span><span>=</span><span> </span><span>&quot;After one draw&quot;</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p><br>
<br>
</p>
<p>The name has been removed from the hat, and the graph is simpler now!</p>
<p>Let’s do it again. Draw a random legal edge (fat arrow) and identify all the<br>
illegal paths (navy).</p>
<div>
<div>
<pre><code><span>current_pick</span><span> </span><span>&lt;-</span><span> </span><span>edges_after_pick1</span><span> </span><span>%>%</span><span> </span><span>draw_secret_santa_edge</span><span>(</span><span>
</span><span>rel</span><span> </span><span>=</span><span> </span><span>&quot;gives-to&quot;</span><span>,</span><span> </span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#FF4136&quot;</span><span>,</span><span> </span><span>penwidth</span><span> </span><span>=</span><span> </span><span>1</span><span>,</span><span>
</span><span>arrowsize</span><span> </span><span>=</span><span> </span><span>1</span><span>)</span><span>
</span><span>current_illegal_edges</span><span> </span><span>&lt;-</span><span> </span><span>edges_after_pick1</span><span> </span><span>%>%</span><span>
</span><span>find_illegal_edges</span><span>(</span><span>edge</span><span> </span><span>=</span><span> </span><span>current_pick</span><span>,</span><span> </span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#001f3f&quot;</span><span>,</span><span> </span><span>penwidth</span><span> </span><span>=</span><span> </span><span>.5</span><span>)</span><span>
</span><span>edges_after_pick1</span><span> </span><span>%>%</span><span>
</span><span>overwrite_edges</span><span>(</span><span>current_pick</span><span>)</span><span> </span><span>%>%</span><span> </span><span>overwrite_edges</span><span>(</span><span>current_illegal_edges</span><span>)</span><span> </span><span>%>%</span><span> </span><span>create_graph</span><span>(</span><span>nodes</span><span>,</span><span> </span><span>.</span><span>)</span><span> </span><span>%>%</span><span> </span><span>render_graph</span><span>(</span><span>title</span><span> </span><span>=</span><span> </span><span>&quot;Selected vs. illegal&quot;</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p><br>
<br>
</p>
<p>After deleting illegal edges, the problem simplifies further.</p>
<div>
<div>
<pre><code><span>edges_after_pick2</span><span> </span><span>&lt;-</span><span> </span><span>edges_after_pick1</span><span> </span><span>%>%</span><span>
</span><span>overwrite_edges</span><span>(</span><span>current_pick</span><span> </span><span>%>%</span><span> </span><span>mutate</span><span>(</span><span>arrowsize</span><span> </span><span>=</span><span> </span><span>NULL</span><span>))</span><span> </span><span>%>%</span><span> </span><span>anti_join</span><span>(</span><span>current_illegal_edges</span><span>,</span><span> </span><span>by</span><span> </span><span>=</span><span> </span><span>&quot;id&quot;</span><span>)</span><span> </span><span>create_graph</span><span>(</span><span>nodes</span><span>,</span><span> </span><span>edges_after_pick2</span><span>)</span><span> </span><span>%>%</span><span> </span><span>render_graph</span><span>(</span><span>title</span><span> </span><span>=</span><span> </span><span>&quot;After two draws&quot;</span><span>)</span><span>
</span></code></pre>
</div>
</div>
<p><br>
<br>
</p>
<p>You can tell where this is going… Loop Town!</p>
<p>To finish up, we are going to repeat this process until there are only<br>
gift-giving edges left. We will control the loop with this helper function<br>
which tells us if there are any free edges remaining.</p>
<div>
<div>
<pre><code><span>has_free_edge</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>edge_df</span><span>)</span><span> </span><span>{</span><span>
</span><span>edges_left</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span> </span><span>%>%</span><span> </span><span>filter</span><span>(</span><span>rel</span><span> </span><span>!=</span><span> </span><span>&quot;gives-to&quot;</span><span>)</span><span> </span><span>%>%</span><span> </span><span>nrow</span><span>()</span><span>
</span><span>edges_left</span><span> </span><span>!=</span><span> </span><span>0</span><span>
</span><span>}</span><span>
</span></code></pre>
</div>
</div>
<p>In the function below, the while-loop does the same steps as above: Randomly<br>
selecting a free edge and removing illegal edges.</p>
<div>
<div>
<pre><code><span>draw_edges_from_hat</span><span> </span><span>&lt;-</span><span> </span><span>function</span><span>(</span><span>edge_df</span><span>,</span><span> </span><span>...</span><span>)</span><span> </span><span>{</span><span>
</span><span>aes_options</span><span> </span><span>&lt;-</span><span> </span><span>quos</span><span>(</span><span>...</span><span>)</span><span>
</span><span>raw_edge_df</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span>
</span><span>indices</span><span> </span><span>&lt;-</span><span> </span><span>unique</span><span>(</span><span>c</span><span>(</span><span>raw_edge_df</span><span>$</span><span>from</span><span>,</span><span> </span><span>raw_edge_df</span><span>$</span><span>to</span><span>))</span><span>
</span><span>while</span><span> </span><span>(</span><span>has_free_edge</span><span>(</span><span>edge_df</span><span>))</span><span> </span><span>{</span><span>
</span><span>pick</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span> </span><span>%>%</span><span> </span><span>draw_secret_santa_edge</span><span>(</span><span>!!!</span><span> </span><span>aes_options</span><span>)</span><span> </span><span>%>%</span><span> </span><span>mutate</span><span>(</span><span>rel</span><span> </span><span>=</span><span> </span><span>&quot;gives-to&quot;</span><span>)</span><span>
</span><span>illegal_edges</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span> </span><span>%>%</span><span>
</span><span>find_illegal_edges</span><span>(</span><span>pick</span><span>)</span><span>
</span><span>edge_df</span><span> </span><span>&lt;-</span><span> </span><span>edge_df</span><span> </span><span>%>%</span><span>
</span><span>overwrite_edges</span><span>(</span><span>pick</span><span>)</span><span> </span><span>%>%</span><span> </span><span>anti_join</span><span>(</span><span>illegal_edges</span><span>,</span><span> </span><span>by</span><span> </span><span>=</span><span> </span><span>&quot;id&quot;</span><span>)</span><span> </span><span>}</span><span>
</span><span>if</span><span> </span><span>(</span><span>!</span><span>has_valid_gift_edges</span><span>(</span><span>edge_df</span><span>,</span><span> </span><span>indices</span><span>))</span><span> </span><span>{</span><span>
</span><span>warning</span><span>(</span><span>call.</span><span> </span><span>=</span><span> </span><span>FALSE</span><span>,</span><span> </span><span>&quot;Invalid drawing. Trying again.&quot;</span><span>)</span><span>
</span><span>edge_df</span><span> </span><span>&lt;-</span><span> </span><span>Recall</span><span>(</span><span>raw_edge_df</span><span>,</span><span> </span><span>!!!</span><span> </span><span>aes_options</span><span>)</span><span>
</span><span>}</span><span>
</span><span>edge_df</span><span>
</span><span>}</span><span>
</span></code></pre>
</div>
</div>
<p>After the while-loop, the function checks if it has a valid set of gift edges,<br>
and if it doesn’t, the function calls itself again. This bit is intended to<br>
handle more constrained situations. Such as…</p>
<h2>The nibling gift exchange</h2>
<p>I lied above. Secret Santa is not so simple in family. For my generation (with<br>
me, my siblings and our partners), there’s a rule that a player can’t draw their<br>
partner’s name. Similarly, my nieces and nephews (and now also my child<br>
:sparkling_heart:) have<br>
their own gift exchange with an added constraint: A player can’t give their<br>
sibling a gift. The elegant and simple Hamiltonian solution fails under these<br>
constraints unless you write a special shuffling algorithm. Our hat-drawing<br>
approach, however, handles this situation with minimal effort. Let’s work<br>
through an example with my nieces and nephews (and :baby:!). To protect the very<br>
young, I have replaced their names with Pokemon names.</p>
<p>Below we define the children and their families and do some data-wrangling so<br>
that we have columns with the family at the start and end of each node.</p>
<div>
<div>
<pre><code><span>niblings</span><span> </span><span>&lt;-</span><span> </span><span>tibble</span><span>::</span><span>tribble</span><span>(</span><span>
</span><span>~</span><span> </span><span>Family</span><span>,</span><span> </span><span>~</span><span> </span><span>Name</span><span>,</span><span> </span><span>~</span><span> </span><span>Number</span><span>,</span><span>
</span><span>&quot;Water&quot;</span><span>,</span><span> </span><span>&quot;Squirtle&quot;</span><span>,</span><span> </span><span>1</span><span>,</span><span>
</span><span>&quot;Water&quot;</span><span>,</span><span> </span><span>&quot;Wartortle&quot;</span><span>,</span><span> </span><span>2</span><span>,</span><span>
</span><span>&quot;Electric&quot;</span><span>,</span><span> </span><span>&quot;Pikachu&quot;</span><span>,</span><span> </span><span>3</span><span>,</span><span> </span><span>&quot;Plant&quot;</span><span>,</span><span> </span><span>&quot;Bulbasaur&quot;</span><span>,</span><span> </span><span>4</span><span>,</span><span> </span><span>&quot;Plant&quot;</span><span>,</span><span> </span><span>&quot;Ivysaur&quot;</span><span>,</span><span> </span><span>5</span><span>,</span><span> </span><span>&quot;Plant&quot;</span><span>,</span><span> </span><span>&quot;Venusaur&quot;</span><span>,</span><span> </span><span>6</span><span>,</span><span> </span><span>&quot;Fighting&quot;</span><span>,</span><span> </span><span>&quot;Machamp&quot;</span><span>,</span><span> </span><span>7</span><span>,</span><span> </span><span>&quot;Fighting&quot;</span><span>,</span><span> </span><span>&quot;Machoke&quot;</span><span>,</span><span> </span><span>8</span><span>,</span><span> </span><span>&quot;Normal&quot;</span><span>,</span><span> </span><span>&quot;Ratata&quot;</span><span>,</span><span> </span><span>9</span><span>,</span><span>
</span><span>&quot;Normal&quot;</span><span>,</span><span> </span><span>&quot;Raticate&quot;</span><span>,</span><span> </span><span>10</span><span>,</span><span>
</span><span>&quot;Psychic&quot;</span><span>,</span><span> </span><span>&quot;Mew&quot;</span><span>,</span><span> </span><span>11</span><span>,</span><span>
</span><span>&quot;Psychic&quot;</span><span>,</span><span> </span><span>&quot;Mewtwo&quot;</span><span>,</span><span> </span><span>12</span><span>)</span><span>
</span><span>nibling_edges</span><span> </span><span>&lt;-</span><span> </span><span>create_all_giving_edges</span><span>(</span><span>
</span><span>niblings</span><span>$</span><span>Name</span><span>,</span><span>
</span><span>rel</span><span> </span><span>=</span><span> </span><span>&quot;potential-gift&quot;</span><span>,</span><span> </span><span>penwidth</span><span> </span><span>=</span><span> </span><span>.5</span><span>,</span><span>
</span><span>color</span><span> </span><span>=</span><span> </span><span>&quot;#CCCCCC90&quot;</span><span>)</span><span> </span><span>%>%</span><span> </span><span>left_join</span><span>(</span><span>niblings</span><span>,</span><span> </span><span>by</span><span> </span><span>=</span><span> </span><span>c</span><span>(</span><span>&quot;from&quot;</span><span> </span><span>=</span><span> </span><span>&quot;Number&quot;</span><span>))</span><span> </span><span>%>%</span><span> </span><span>rename</span><span>(</span><span>from_fam</span><span> </span><span>=</span><span> </span><span>Family</span><span>)</span><span> </span><span>%>%</span><span> </span><span>select</span><span>(</span><span>-</span><span>Name</span><span>)</span><span> </span><span>%>%</span><span> </span><span>left_join</span><span>(</span><span>niblings</span><span>,</span><span> </span><span>by</span><span> </span><span>=</span><span> </span><span>c</span><span>(</span><span>&quot;to&quot;</span><span> </span><span>=</span><span> </span><span>&quot;Number&quot;</span><span>))</span><span> </span><span>%>%</span><span> </span><span>rename</span><span>(</span><span>to_fam</span><span> </span><span>=</span><span> </span><span>Family</span><span>)</span><span> </span><span>%>%</span><span> </span><span>select</span><span>(</span><span>-</span><span>Name</span><span>)</span><span> </span><span>%>%</span><span> </span><span>select</span><span>(</span><span>id</span><span>,</span><span> </span><span>from</span><span>,</span><span> </span><span>to</span><span>,</span><span> </span><span>rel</span><span>,</span><span> </span><span>from_fam</span><span>,</span><span> </span><span>to_fam</span><span>,</span><span> </span><span>everything</span><span>())</span><span>
</span><span>nibling_edges</span><span>
</span><span>#> # A tibble: 132 x 8</span><span>
</span><span>#> id from to rel from_fam to_fam penwidth color</span><span>
</span><span>#> </span></code></pre></div></div>