» Secret Santas in Haskell II: Orbits and Lists #

Paul R. Brown @ 2006-12-17

Part I set up a data structure and covered input and output, so it's back to the problem at hand. This post establishes a useful equivalence and establishes a strong condition on the existence of a solution.

From Orbits to Lists

From a purely academic perspective, it's worth observing that there aren't always solutions to the Secret Santa problem. For example, the degenerate case of only a single family is one unsolvable case, but it's also the case that if a single family comprises more than half of the participants, then there is no solution (by the pigeonhole principle). A more useful observation is that the problem of a mapping can easily be turned into a problem of lists.

First, observe that if there is a circular list that contains each of the members of P (the set of participants from Part I) exactly once where no two consecutive list elements have the same last name, then the successor function is a secret santa function. Conversely, if there is any secret santa function, it can be used to generate such a list, as follows. (It is not the case that every secret santa function arises from a list.) For a secret santa function s, the orbits of elements of P are a finite number of disjoint subsets, each of which has the form a of a circular list of elements of P where no two consecutive elements have the same last name. If there are at least two orbits O1 and O2, combine the two of them by breaking each orbit at a randomly selected element and concatenating the two lists head-to-tail and tail-to-head to get a new circular list, like so:

If O1 merged with O2 violates the successor condition, then O1 merged with O2 in reverse order does not. Sketch the cases on a piece of paper if this isn't obvious; in brute-force terms, it would look something like this:

The two colors squares in a column or row heading represent the "ends" of the broken circular lists, and concatenation is performed by gluing the two entries touching the table and the two entries not touching the table; a yellow square indicates that one of the lists should be reverse prior to gluing. For example, the upper left square would be R...G + G...R or, after reversing the second list, R...G + R...G, which is a legal combination.

This proves that if there is a secret santa function that decomposes the set into n>1 orbits, then there is a secret santa function that decomposes it into n-1 orbits. Thus, to create a solution, it's enough to create a circular list that exhausts P and where no two markers are repeated.

Orbits and Drafting

The observation above about there being no solution when one family is larger than the sum of all of the other families can be strengthened: that is the only case when there is no solution. The idea of the proof is to sort the families by size and then draft members from the smallest family into the second largest family, as depicted below:

In the image, each layer is an orbit, and the diagram up to the top of the yellow-green (i.e., second largest) family represents a valid secret santa function. The yellow-green family can continue to draft members from the smallest family until either the yellow-green and dark red families are the same size or until the smaller families are exhausted, i.e., the dark red family contains more members than the other families combined.

As an aside, a similar strategy works to obtain an as-rectangular-as-possible arrangement:

In Practice

Up next, a couple of posts (like this one, in the secretsanta tag) with solutions implemented using these ideas.

 

← 2006-12-17 — Secret Santas in Haskell I: Preliminaries
→ 2006-12-22 — Secret Santas in Haskell III: Lather, Rinse, Repeat