A fair Secret Santa draw with exclusions is a matching problem

A Secret Santa draw looks like a shuffle. It stops being one the moment someone says "Ana and Ben are a couple, they can't draw each other" and "nobody gets the same person as last year".

I built the Secret Santa generator on Toggle9 and ended up with three small problems hiding inside it:

1. Is a draw possible at all with these rules, and if not, why not, in words a person can act on?
2. How do you pick one so that every valid draw is equally likely?
3. How many valid draws are there? It turns out people like knowing.

All of it is pure functions over a 0/1 matrix, with no DOM, and randomness passed in so tests can seed it.

The model: an "allowed" matrix

A[i][j] is true when person i may buy for person j. Start with everything allowed except yourself, then switch off exclusions and last year's pairs:

export function allowedMatrix(people, avoid = {}) {
  const idx = new Map(people.map((p, i) => [p.n.toLocaleLowerCase(), i]));
  const A = people.map((_, i) => people.map((__, j) => i !== j));
  people.forEach((p, i) => {
    for (const x of p.no || []) { const j = idx.get(String(x).toLocaleLowerCase()); if (j !== undefined) A[i][j] = false; }
    const last = avoid[p.n];
    if (last !== undefined) { const j = idx.get(String(last).toLocaleLowerCase()); if (j !== undefined) A[i][j] = false; }
  });
  return A;
}

A draw is then a permutation to where A[i][to[i]] holds for everyone. With no extra rules that's a derangement: a permutation with no fixed points. For 6 people there are 265 of them out of 720 shuffles, about 36.8%. (That ratio tends to 1/e, which is why "shuffle until nobody has themselves" works fine for small groups.)

1. Is it possible? Matching, plus Hall's theorem for the "why"

Whether some valid draw exists is a bipartite matching question: givers on one side, receivers on the other, edges where A allows. Kuhn's augmenting-path algorithm answers it in a few lines.

The more interesting part is what to say when it fails. "No valid draw" is useless to a group organiser. Hall's theorem says a perfect matching fails to exist exactly when some group of k givers can only reach fewer than k receivers. And the failing run of Kuhn's algorithm hands you that group: everything reachable from the stuck giver along alternating paths.

for (let i = 0; i < n; i++) {
  if (tryAug(i, Array(n).fill(false))) continue;
  // i cannot be placed: everything reachable from i by alternating paths is the Hall violator
  const gs = new Set([i]), rs = new Set(), queue = [i];
  while (queue.length) {
    const g = queue.shift();
    for (let j = 0; j < n; j++) if (A[g][j] && !rs.has(j)) {
      rs.add(j);
      const m = rec[j];
      if (m >= 0 && !gs.has(m)) { gs.add(m); queue.push(m); }
    }
  }
  return { ok: false, givers: [...gs], receivers: [...rs] };   // receivers.length < givers.length
}

Small example: three people, and Ana and Ben may not draw each other. Ana can only buy for Cal, and so can Ben. The function returns givers: [Ana, Ben], receivers: [Cal], which the page turns into a sentence: Ana and Ben can only buy for Cal: 2 people, 1 person to buy for. Now the organiser knows which rule to drop.

2. Picking one fairly: rejection sampling

The tempting approach is to assign people one at a time, picking a random allowed receiver for each and backtracking when stuck. It finds a draw quickly, but not uniformly: early givers' choices skew who is left for later givers, so some valid draws come up more often than others.

The simplest fair method is also the oldest: shuffle (Fisher–Yates), check against the rules, and try again if it fails.

for (let t = 1; t <= maxTries; t++) {
  const to = shuffle(base.slice(), rnd);
  if (isValid(to, A, opts)) return { to, exact: true, tries: t };
}

Every permutation is equally likely from the shuffle, and we keep only the valid ones, so every valid draw is equally likely too. For a typical office or family group this succeeds within a handful of tries. In a 6-person test with two couples, it took 2.

The catch is a group with so many rules that valid draws are a tiny fraction of all shuffles. After 400,000 tries the code falls back to a randomised depth-first search plus random valid swaps (40·n² attempts), and reports exact: false rather than pretending the result is perfectly uniform. In practice only heavily constrained groups ever reach it.

rnd is passed in: the page uses crypto.getRandomValues, and the tests pass a seeded generator so a draw can be replayed.

Variants: "one big circle" and "no swapping pairs"

Two options change the shape of a valid draw:

• One big circle: Ana → Ben → Cal → … → Ana, so gifts can be opened in a chain. Now a draw is a directed Hamiltonian cycle in the allowed graph, not just any permutation. The shuffle step generates a random cycle order instead of a random permutation.
• No swaps: if Ana buys for Ben, Ben shouldn't buy for Ana. That forbids 2-cycles.

Both plug into the same isValid check, so the rejection-sampling loop stays the same.

3. Counting the draws

Showing "there are 116 possible draws" is a small thing, but it reassures people that the rules haven't boxed the draw in. Counting depends on the variant:

• Plain draw: the number of perfect matchings is the permanent of A. Ryser's formula with a Gray-code walk computes it in O(2ⁿ·n). The intermediate terms overflow exact double precision from about 13 people, so larger groups switch to BigInt (the final count is still small enough for a Number).
• Circle: count Hamiltonian cycles with a bitmask DP over subsets, fixed to start at person 0.
• No swaps: brute force for up to 9 people.

Above 16 people the page simply doesn't show a count, because 2ⁿ stops being quick enough.

For the same 6 people with two couples who can't draw each other:

Rules	Valid draws
Couples excluded	116
Couples excluded + one big circle	48
Couples excluded + no swaps	64

The reveal links

Once drawn, each person gets their own link with their match encoded after the #, so it is never sent to a server. The text is XOR-scrambled with a random salt so a name doesn't show in a chat preview. That is not encryption, and the page says so: it stops accidental peeking, not a determined snoop.

Tests

The draw has its own test file in Node's built-in node:test, with a seeded random generator so every run is repeatable:

• counts match the derangement numbers (OEIS A000166) with no rules, and brute force with rules, including the BigInt path at 13–16 people;
• impossible groups must name the givers and receivers that cause it;
• every returned draw must pass isValid, in every mode;
• fairness: 4 people have 9 possible draws, so 18,000 seeded draws should land on each of them 2,000 times, give or take 10%.

If you'd like to try the edge cases, the generator is free with no sign-up. Three people where two can't draw each other is the quickest way to see the "why not" message.