secret-santaclaus

Secret Santa organiser with MCMC random sampling of arbitrary constraints and email utilities.

Usage

secret-santaclaus is a Python package for generating near-uniformly random Secret Santa allocations from a set of participants and a set of arbitrary constraints upon who can be allocated to whom. It also includes a built-in utility for secretly sending emails to participants with their allocated recipients.

This package is published to PyPI for easy installation via pip (or any other package manager), e.g.:

pip install secret-santaclaus

See example.py for a simple walkthrough of using the package to configure a Secret Santa model of participants and constraints, generate a solution by sampling a Markov-chain Monte Carlo (MCMC) method, and email participants their allocations via an SMTP mail server. It also demonstrates how each of these can either be defined directly in the Python API, or loaded to/from YAML files.

Methodology

In Secret Santa, participants are randomly and secretly allocated to give each other a gift. This is not a complicated problem to solve: it's just random selection without replacement. Let's say you wanted to impose arbitrary constraints, however, such as couples not being able to get each other as an allocation (because that would be boring!).

This Python package solves this problem by modelling the set of participants as a directed graph, where every edge in the graph represents a valid allocation. For example, if Alice and Bob are couples, as are Charlie and Dan, and as are Eve and Frank, this model graph, $G_m$, would resemble a complete graph with edges between couples removed (Figure 1).

A valid Secret Santa allocation is therefore a vertex cycle cover on $G_m$. Finding a vertex cycle cover is equivalent to finding a perfect matching on the corresponding factor graph, which we define as a bipartite graph $G_f = (V_L, V_R, E)$ with each node in $G_m$ 'copied' into both sides $V_L$ and $V_R$, and with each edge $(u,v)$ in $G_m$ represented by an edge $(u_L, v_R)$ (Figure 2). A perfect matching can be found in polynomial time, yielding a valid solution (Figures 3 and 4).

Figure 1: Model graph $G_m$ with no edges between couples.	Figure 2: Bipartite factor graph $G_f$.
Figure 3: A valid solution is a vertex cycle cover on the model graph.	Figure 4: A vertex cycle cover on the model graph is a perfect matching on the factor graph.

However, algorithms for finding a perfect matching are generally designed as optimisation methods, usually to find a minimum/maximum weight/cardinality. In this case, we aren't interested in an optimal solution, but in fact want to generate random solutions.

This package implements near-uniformly random sampling of bipartite perfect matchings by a Markov-chain Monte Carlo (MCMC) method given by Jerrum and Sinclair (1989). The solver by default progresses the MCMC state before yielding a solution by at least the mixing time, which is calculated from the size of the problem instance.