A Secret Santa draw is a constraint puzzle, not a shuffle
Every December, someone writes a Secret Santa script in ten lines: build a list of names, shuffle it, zip it against itself, check nobody drew themselves, retry if they did. It works for eight people. It falls apart the moment the group has couples, a "no family" rule, or an odd number of participants.
That is not a coding accident. It is the difference between shuffling and solving a constraint problem.
The shuffle version and why it fails
The ten-line version treats the draw as a permutation and keeps rerolling until the permutation has no fixed point. For a plain draw that is fine: the chance a random permutation of n people has no one drawing themselves is about 1/e, so you expect a couple of retries.
Add one rule — "nobody draws their partner" — and rejection sampling stops being cheap. Add five rules and the loop starts spinning: most random permutations now violate at least one exclusion, and the script has no idea whether it is failing because of bad luck or because the rule set is impossible.
The worst case is not bad luck. Two people who exclude everyone except each other can only be matched with each other, and if they are partners the instance has no solution at all. A retry loop will spin forever; a person watching it will assume the site is broken.
Model the draw as a graph
Write the group as a directed graph: an edge from A to B means "A is allowed to give to B". A valid draw is a set of edges where every person gives exactly once and receives exactly once — a perfect matching, with the extra condition that A to A is never allowed.
Now the rules are just edges you delete. Partners: delete both directions between them. Department rules, "not my ex", "not the person who had me last year": all the same operation. The puzzle is not "shuffle until it looks random", it is "find a perfect matching in a sparse graph".
That reframing buys three things a shuffle cannot give you:
- Feasibility before the draw. If a matching does not exist, you can say so before anyone opens a link. Hall's condition gives the practical test: for every subset S of givers, the number of receivers reachable from S must be at least |S|. In practice you check the small suspects — the pair with one option each, the person everyone excluded — and you tell the organizer which rule to relax.
- No retry storms. Backtracking with a most-constrained-first order picks the person with the fewest remaining options, assigns them, and undoes the assignment when it hits a dead end. On the group sizes Secret Santas actually have, this finishes in microseconds.
- Secrecy that survives inspection. A shuffled list has to be cut into per-person messages. A matching is already edge-shaped: each edge becomes one private link, and the organizer's copy never needs to contain the whole answer.
The two-person dead end, in detail
Here is the case that breaks naive implementations most often, and it is not rare in offices: two participants each exclude everyone but the other, and they also exclude each other. Each has exactly one outgoing edge and that edge is forbidden by the second rule, so both have zero options. A backtracking solver reaches that state in one step and returns "impossible". A retry loop returns nothing, forever.
The fix is not a better random seed. It is to detect zero-option nodes before assigning anything, and to explain the conflict in the organizer's language: "Ana and Ben can only draw each other, but they opted out of drawing each other."
What this changes in the UI
Once the draw is a solver, the product decisions change too:
- Rules belong to people, not to the group. Each participant states their own exclusions when they join; the organizer does not need to know who is partnered with whom.
- The result is a link, not a list. Nobody — including the organizer — needs to see a full mapping. Each person gets one URL that reveals one name.
- Failure is a message, not a spinner. When the rules make a draw impossible, the organizer gets the conflicting pair and a suggested relaxation, not a retry button.
That is the whole design of the Secret Santa generator we built: exclusions per person, a solver instead of a shuffle, and one private link per participant, with no email list collected. If you want to see the constraint logic in the context of a full group, the exclusions organizer walks through the impossible cases; the generator itself is free and runs in the browser.
The takeaway
If you are writing the draw yourself this year, the ten-line shuffle is fine until someone adds a rule. The moment a group has couples, the draw is a matching problem, and matching problems want a solver, a feasibility check, and an error message that names the conflict. That is maybe forty lines instead of ten, and it is the difference between "try again" and a draw that cannot fail silently.