Derangements and the Secret Santa Problem

How often a shuffle accidentally works

Take any group and shuffle their names to decide who buys for whom. The chance that nobody ends up with their own name is the proportion of permutations that are derangements — and that proportion converges very fast on 1 divided by e, about 0.3679.

The convergence is remarkably quick. For four people it is 0.3750; for five it is 0.3667; for six it is 0.3681; and from about seven onwards it is 0.3679 to four decimal places. The size of the group essentially stops mattering after six.

So the practical statement is: a plain shuffle produces a valid gift exchange about 37% of the time, whether your group is eight people or eighty. Which means it fails about 63% of the time, and "just shuffle and check" is a coin flip you lose more often than you win.

The expected number of self-draws is always one

Here is the result that surprises people most. In a random shuffle of n names, the expected number of people who draw themselves is exactly 1 — regardless of how large n is.

The argument is short. Each individual person has a 1-in-n chance of landing back on their own name. There are n people. Expectation adds regardless of whether the events are independent, so the expected count is n multiplied by 1/n, which is exactly 1.

That holds for a group of five and a group of five hundred. It is the same result behind the seat-rotation tool: reshuffling a class of thirty leaves, on average, exactly one student in their original seat — and it would leave exactly one on average in a class of three hundred.

Generating a derangement

The practical method for group sizes people actually use is randomised restart: shuffle, check whether anyone drew themselves, and reshuffle if so. Since about 37% of shuffles qualify, you expect to succeed in about 2.7 attempts, and the probability of needing more than twenty attempts is under one in ten thousand.

There are dedicated algorithms that generate a derangement directly in one pass, and they matter for large n or for a context where a bounded worst case is required. For a gift exchange with fourteen people in a browser, restart is simpler, obviously correct, and fast.

The important property of restart here is that it samples uniformly among derangements — each valid arrangement is equally likely, because each shuffle was uniform and the test does not favour any particular derangement. That is a stronger guarantee than the constrained version gets once exclusions are added.

The 'hat' method and why it is worse

The traditional physical method is to write names on slips, put them in a hat, and have each person draw one, redrawing if they get themselves. This is not a derangement algorithm and it has a failure mode people rediscover every December.

The problem is the last person. If everyone before them has drawn, and the only slip left is their own name, they must redraw — but there is nothing to redraw from, so the whole draw has to restart. That happens with probability roughly 1/n each round, and with a room full of people who have already looked at their slips, restarting is socially expensive.

The partial fix used by most groups — letting the last person swap with someone — is not uniform. It biases the outcome toward arrangements involving that swap, in a way nobody tracks. A generated derangement has neither problem.

• The hat method fails outright when the last slip is the last person's own name.
• That happens with probability roughly 1/n per full draw.
• The usual fix — a swap with a volunteer — biases the result in an untracked way.
• A generated derangement is uniform and never needs restarting in public.

Adding exclusions makes it a different problem

The moment you add "couples must not draw each other", the problem stops being a derangement and becomes a general constrained assignment. The clean 1/e mathematics no longer applies, the valid fraction depends on the specific exclusion structure, and — crucially — a valid answer may not exist at all.

Couples alone are rarely the problem, which surprises people. Two couples, three couples and four couples all have valid arrangements — six people in three couples can be assigned as two three-cycles, and nobody draws a partner. The genuine exception is a single couple on their own, where each person's only possible recipient is the other.

Failure comes instead from a bottleneck: several givers funnelled onto the same small set of recipients. Three people in a group of four, each barred from the other two, all have to draw the remaining person — and one recipient cannot absorb three givers. That is Hall's condition failing, and no algorithm recovers from it.

This is why a gift exchange with exclusions needs a tool that can report failure. A derangement always exists for n ≥ 2; a constrained assignment does not, and pretending otherwise means quietly violating a rule somebody set.

Frequently asked questions

Tools that use this

Related guides