Secret Santa Generator

Introduction to derangements and the Secret Santa draw

A Secret Santa draw looks like a party game, but it is a precisely specified combinatorial object. Number the participants 1 to n and let the assignment be a function that sends each giver to the person they buy for. Because every participant gives exactly one gift and receives exactly one gift, that function must be a permutation of the roster. Because nobody may draw their own name, the permutation must have no fixed point. A permutation with no fixed point is called a derangement, and it is the exact mathematical object this generator produces.

Two things follow immediately, and both are things most online Secret Santa tools get wrong. First, the number of legal draws is not n! but the subfactorial !n, which is roughly 37% of n!. Second — and this is the subtle one — producing a derangement is easy, but producing a uniformly random derangement is not. A generator that always returns the same shape of answer, or that returns some legal answers far more often than others, is biased even though every individual output it prints looks perfectly valid. The draw only feels fair if every legal assignment really was equally likely, and that property has to be engineered deliberately.

This page runs entirely in your browser. The roster never leaves your device, there is no account, no email collection and no server round-trip, so you can run the draw with the network switched off. Below the tool you will find the inclusion–exclusion derivation of !n, a description of the exact sampling algorithm used, the reason the popular shortcuts are biased, and how exclusion rules turn the problem into a bipartite matching that can be infeasible.

How to use the generator and hand out the results

Paste one participant name per line into the roster box. Blank lines are ignored and surrounding spaces are trimmed. Duplicate names are rejected rather than silently accepted, because two people recorded as "Alex" cannot be told apart by the assignment, by you, or by the person holding the slip — add a surname or an initial instead.

If some pairs must never be matched, list them in the exclusion box, one rule per line, with the two names separated by a vertical bar, for example Priya | Sam. Each rule is treated as mutual by default: Priya will not draw Sam and Sam will not draw Priya. Untick Treat each rule as mutual if you want a one-directional rule instead, which is useful when you are only blocking last year's pairing. The generator checks whether your rules can be satisfied at all before it starts drawing, and tells you which names are over-constrained if they cannot.

Press Draw assignments. The result panel reports the assignment table, the exact number of legal draws for your roster, the probability that this particular assignment came up, the cycle structure of the draw and how many shuffles the sampler needed. Use Copy one private slip to place a single giver's line on the clipboard so you can message each person individually without revealing anyone else's target, Download CSV for the organiser's master copy, and Copy setup link to share the roster and rules with a co-organiser. The setup link deliberately stores no assignment and no random seed, so opening it reproduces the inputs but forces a fresh draw.

The subfactorial formula and why uniform sampling matters

Count the derangements by inclusion–exclusion. Let A_i be the set of permutations that fix element i. There are (n − k)! permutations fixing any chosen k elements, and C(n, k) ways to choose them, so subtracting and re-adding the overlaps gives the subfactorial:

The bracketed sum is the truncated Maclaurin series for e⁻¹, so the density of legal draws among all permutations settles down almost immediately:

The convergence is fast enough to be startling. At n = 5 the ratio is 44/120 = 0.36667; at n = 8 it is 14833/40320 = 0.367882; by n = 10 it agrees with 1/e to six decimal places. Two exact recurrences, both proved by Euler in 1809, make !n cheap to evaluate without any floating-point rounding:

This page evaluates the first recurrence in BigInt arithmetic with the base cases !0 = 1 and !1 = 0, so the count it prints is exact for every roster size, not a rounded n!/e. Note the base case !1 = 0: a one-person exchange has no legal draw at all, which is why the form insists on at least two names.

How the draw is actually sampled

The sampler is deliberately boring, because boring is what makes it correct. It performs a Fisher–Yates shuffle of the roster positions — drawing each index uniformly from the remaining range with Math.floor(Math.random() * (i + 1)), which is the unbiased form, not the modulo form — and then checks whether the shuffle happens to be a derangement. If it is not, it throws the whole shuffle away and starts again. This is rejection sampling, and it is uniform for the trivial reason that every derangement is produced by exactly one of the equally likely shuffles that survive the filter.

Rejection sampling sounds wasteful and is not. The acceptance probability is exactly !n/n!, so the expected number of shuffles is n!/!n, which converges to e:

Fewer than three shuffles on average, at any group size, for a total cost of O(n) expected work. There is no scaling reason to reach for anything cleverer.

Why the two popular shortcuts are wrong

The first shortcut is shuffle then rotate: shuffle the list and hand each person the next name along. Every output is a valid derangement, so the bug is invisible in testing. But a rotation is a single n-cycle, so the method can only ever emit the (n − 1)! permutations that consist of one cycle. For six people that is 120 of the 265 legal draws; the other 145 are unreachable no matter how well you shuffle. It can never produce an assignment made of two disjoint 3-cycles, for instance, even though 40 of the 265 legal draws have exactly that shape. Rotating a fixed roster by a random offset instead is worse still: it reaches only n − 1 assignments in total. This is CLRS exercise 5.3-4 (PERMUTE-BY-CYCLIC), whose entire point is that a cyclic shift does not give a uniform random permutation. Sattolo's 1986 algorithm is the correct way to sample a single cycle, but it is uniform over cyclic permutations, which is a different distribution from uniform over derangements.

The second shortcut — and the one this page previously used — is shuffle then repair: shuffle, then wherever somebody drew themselves, swap them with a neighbour. Again every output is legal, and again the distribution is badly skewed, because the repair step funnels many distinct shuffles onto the same few derangements. Enumerating all 24 permutations of a four-person roster under that repair rule gives probabilities ranging from 1/24 to 8/24 across the nine legal draws, against a uniform 1/9 ≈ 2.67/24. One assignment was eight times more likely than another. At n = 5 the worst-case ratio is 13:1. Anyone who ran the draw twice and noticed the same person kept receiving from the same person would have been right to be suspicious.

Exclusion rules turn the draw into a matching problem

Once couples, housemates or last year's pairs are barred from each other, the object being counted stops being a derangement and becomes a permutation with restricted position. Stanley develops exactly this generalisation in Enumerative Combinatorics §2.3 using rook polynomials: place the forbidden pairs on a board B ⊆ [n] × [n], and the number of legal assignments is the permanent of the 0–1 matrix that has a 1 wherever a giver may draw a recipient. The plain derangement problem is the special case where B is just the diagonal.

The practical consequence is that a constrained draw can be impossible, and that the impossibility is not always obvious. Take four people where Ana, Ben and Caz are all barred from one another: those three can only give to Dee, but Dee can receive from just one of them, so no assignment exists. This is a violation of Hall's condition. Naive rejection sampling in that situation does not fail — it spins forever, which is why several Secret Santa tools freeze the browser tab on over-constrained rosters. This page instead runs a Kuhn augmenting-path search for a perfect matching in the bipartite graph of allowed giver–recipient pairs first, and only starts sampling once feasibility is proved. If the matching fails it names the group of givers whose combined set of permitted recipients is too small.

Once feasibility is established, the sampler keeps rejecting until it lands on an assignment satisfying every rule, which remains exactly uniform over the legal set. Because heavy constraints can make the acceptance rate very small, the loop is capped; if the cap is reached the page falls back to a randomised backtracking construction, which always succeeds when a solution exists but is not guaranteed uniform. When that happens the result panel says so explicitly rather than quietly presenting a biased draw as a fair one.

Worked example: seven colleagues with two exclusion rules

A team of seven — Ana, Ben, Caz, Dee, Eli, Fay, Gus — runs an exchange. Ana and Ben share a desk and already buy each other birthday presents, and Fay drew Gus last year. So there are two rules: Ana | Ben (mutual) and Fay | Gus (mutual).

Start with the unconstrained count. Using !n = (n − 1)(!(n − 1) + !(n − 2)) from !0 = 1 and !1 = 0: !2 = 1, !3 = 2, !4 = 9, !5 = 44, !6 = 265, and !7 = 6 × (265 + 44) = 6 × 309 = 1854. Check it against 7!/e = 5040 / 2.718282 = 1854.11, which rounds to 1854 — this matches OEIS A000166 term by term.

Now impose the four forbidden ordered pairs (Ana→Ben, Ben→Ana, Fay→Gus, Gus→Fay) on top of the seven forbidden self-pairs. The forbidden cells are no longer just the diagonal, so !7 no longer applies; the count is now the permanent of the 7 × 7 matrix that carries a 1 in every allowed giver–recipient cell. The tool evaluates that permanent exactly and reports 920 legal assignments — 49.6% of the unconstrained 1854, so those two innocuous-looking rules eliminate half the sample space. Each surviving assignment is drawn with probability 1/920 ≈ 0.001087, and the sampler needs 5040/920 ≈ 5.5 shuffles per accepted draw, still trivial work.

A typical output is Ana→Dee, Ben→Fay, Caz→Ana, Dee→Gus, Eli→Caz, Fay→Eli, Gus→Ben. No name appears opposite itself, no barred pair appears, and every name occurs exactly once in each column. Reading the giver→recipient arrows as a walk gives Ana → Dee → Gus → Ben → Fay → Eli → Caz → Ana: one cycle of length 7. That is the most common shape for seven people, but not the only one — a draw of 3 + 4 or 2 + 5 is equally admissible and the tool will report it when it happens.

Interpreting the result: cycles, odds and repeat years

The number the result panel calls legal assignments is the size of the sample space, and 1 divided by it is the probability that this exact assignment was the one drawn. For a group of ten that probability is roughly 1 in 1.33 million; the point is not that the draw is rare but that no assignment was favoured.

The cycle structure line is the most informative and least understood output. Every permutation decomposes uniquely into disjoint cycles, and a derangement has no cycle of length 1. A single long cycle means everyone is linked in one chain — nice if you plan to reveal the chain at the end of the party. Several short cycles mean the group has split into independent sub-exchanges; a 2-cycle in particular is a mutual pair, where two people happen to buy for each other. Mutual pairs are legal derangements and they are common: the expected number of 2-cycles in a uniformly random derangement is C(n,2)·!(n−2)/!n, which is 0.5094 at n = 6 and settles to 0.5000 from about n = 10 onward. In other words roughly half of all draws contain one. Some organisers dislike them. If you are one of them, ticking Avoid mutual pairs restricts the sample space to derangements whose shortest cycle has length at least 3 — OEIS A038205, counted by !!₃(n) = (n−1)·!!₃(n−1) + (n−1)(n−2)·!!₃(n−3) — and the tool recomputes the count and the odds for that restricted space rather than pretending the probability is unchanged. For six people that drops the sample space from 265 to 160.

The shuffles used line is a live confirmation that the sampler is doing what this page claims: over repeated draws it should average near e ≈ 2.72 for an unconstrained roster, and higher when exclusions bite. If you ever saw it stuck at 1 every time, the sampler would not be rejecting anything and the draw would not be uniform.

Limitations, assumptions and privacy caveats

The randomness comes from Math.random(), which in every current browser engine is a fast non-cryptographic PRNG (xorshift128+ or similar). It is statistically fine for a gift exchange and produces no detectable bias in the draw. It is not a cryptographic random source, so this tool is not appropriate for a draw with money or legal consequences riding on it, where you would want crypto.getRandomValues and an auditable commitment scheme.

The draw is memoryless. It knows nothing about previous years except the exclusion rules you type in, and it does not balance who has already given to whom over time. Multi-year fairness is a different optimisation problem and is not modelled here.

Uniformity is guaranteed for unconstrained rosters and for constrained rosters that clear the rejection cap. If the cap is exhausted and the backtracking fallback runs, the assignment is valid but its distribution is unspecified; the panel flags this. Exact counting under exclusions is a permanent computation, which is #P-complete in general. The tool evaluates it exactly with a subset-sum dynamic program for rosters up to 18 people; beyond that, or when exclusions and the no-mutual-pairs option are combined, it says the exact count was not computed instead of printing a guess. The sampling itself is unaffected and stays uniform either way.

Finally, the privacy limits. Everything runs client-side and nothing is transmitted, but the organiser inevitably sees the whole table. If you want nobody to know the full mapping, this tool cannot give you that — you would need an interactive protocol, not a static page. The setup link is safe to pass to a co-organiser because it contains the roster and the rules but never the assignment and never a seed; a link that carried a seed would let any recipient regenerate the entire draw, which is precisely why this page does not offer one. Names typed into the roster do end up in your browser's session history for the tab, so use the reset button on a shared machine.

Questions organisers ask before running the draw

Derangement counts for common group sizes

Sources. Derangement counts and both Euler recurrences: The On-Line Encyclopedia of Integer Sequences, sequence A000166 — "Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points", OEIS Foundation Inc.; the entry states a(n) = n!·∑_k=0..n (−1)^k/k!, a(n) = (n−1)(a(n−1)+a(n−2)), a(n) = n·a(n−1)+(−1)ⁿ, and a(0)=1, a(n)=round(n!/e). Derangements with no mutual pair: OEIS A038205 — "Number of derangements of n where minimal cycle size is at least 3", recurrence a(n) = (n−1)·a(n−1) + (n−1)(n−2)·a(n−3). Inclusion–exclusion derivation and the restricted-position generalisation: Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2011, Example 2.2.1 (equations 2.11–2.14) and §2.3 "Permutations with Restricted Position", author's edition, MIT. Fisher–Yates uniformity and the non-uniformity of a cyclic shift: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, §5.3 "Randomly permuting arrays" (RANDOMIZE-IN-PLACE and Lemma 5.5) and exercise 5.3-4 (PERMUTE-BY-CYCLIC); the algorithm itself is catalogued by the US National Institute of Standards and Technology, Dictionary of Algorithms and Data Structures: "Fisher-Yates shuffle", citing Fisher & Yates, Statistical Tables (1938) and Knuth, TAOCP Vol. 2, Algorithm 3.4.2P. Uniform generation of a single cycle: Sandra Sattolo, "An algorithm to generate a random cyclic permutation", Information Processing Letters 22(6):315–317, 30 May 1986.