Secret Santa is a graph problem: drawing names with "not my partner" rules

Drawing names for Secret Santa sounds like a one-liner: shuffle the list and you're done. Then the rules arrive. Nobody can draw themselves. Couples shouldn't draw each other. The two people who sit next to each other all year want someone new. And when the rules can't all be met, the tool has to say so instead of spinning forever.

Our small team built a free Secret Santa generator that runs entirely in the browser, and the draw ended up being a nice little algorithms problem. This post walks through it: why the paper-hat method breaks, what "fair" means here, and how a classic graph algorithm handles the hard cases.

The paper hat has a bug

The classic method: everyone pulls a name from a hat, and if you pull your own, you put it back and draw again.

Run that with four people. Suppose the first three draw fine, and the last slip in the hat is the fourth person's own name. There's nobody left to swap with, so the whole draw starts over, and everyone has already seen a name. A program that copies the hat, one person at a time, hits the same dead end.

So don't draw person by person. Draw the whole assignment at once and check it.

What we're actually generating

Number the people 0..n-1. A draw is an array where draw[giver] = receiver. Every person gives once and receives once, so the array is a permutation. Nobody gives to themselves, so it's a permutation with no fixed points: a derangement.

Derangements are common. Of all n! permutations, the share that are derangements quickly settles at 1/e, about 36.8%:

That gives the simplest correct algorithm: shuffle, check, repeat.

type Rng = () => number; // uniform in [0, 1)

const shuffle = <T>(items: T[], rng: Rng): T[] => {
  const out = items.slice();
  for (let i = out.length - 1; i > 0; i--) {
    const j = Math.floor(rng() * (i + 1));
    [out[i], out[j]] = [out[j], out[i]];
  }
  return out;
};

Given a uniform rng, a Fisher–Yates shuffle gives every permutation the same chance. Keep the first one that's a derangement, and every derangement has the same chance too, because rejection doesn't favour any of the survivors. With no extra rules, one try succeeds about 37% of the time, so on average you need about three.

(One footnote for the pedantic, and fair enough: Math.floor(rng() * k) over a 32-bit random value can't split 2^32 values evenly into k buckets unless k is a power of two. At 50 people the skew is below about 1 part in 10^8. Rejection sampling on the integer itself removes it, if you want it gone entirely.)

Why not just make one big circle?

There's a popular shortcut: shuffle the names, then have each person give to the next one in the list, and the last give to the first. It never fails and needs no retries.

It's valid, but it only produces one kind of draw: a single loop through everyone. It can never pair two people as each other's Santa, or split a group of six into two loops of three. With 4 people there are 9 derangements, and the circle can only produce 6 of them. At 8 people it's 5,040 out of 14,833.

That's a matter of taste, not a bug. Some groups like the single chain because you can reveal it in order at the party. We wanted every valid draw to be possible, so we kept rejection sampling.

Adding "not my partner"

Exclusions are pairs that mustn't draw each other, in either direction. Store everything as an allowed matrix:

type Exclusion = readonly [number, number];

const allowedMatrix = (n: number, exclusions: readonly Exclusion[]) => {
  const allowed = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => i !== j),
  );
  for (const [a, b] of exclusions) {
    if (a >= 0 && b >= 0 && a < n && b < n) {
      allowed[a][b] = false;
      allowed[b][a] = false;
    }
  }
  return allowed;
};

The check becomes perm.every((receiver, giver) => allowed[giver][receiver]), and rejection sampling still works. It just gets slower as the rules pile up:

• 4 couples (8 people), nobody draws their partner: 4,752 valid draws out of 40,320, about 11.8%. Still fine.
• Two teams of 4, everyone must draw from the other team: 576 valid draws, about 1.4%. Getting rare.
• 3 people, and person 0 can't draw either of the others: zero valid draws. Rejection sampling would loop forever.

That last case is the real problem. With a retry loop alone you can't tell "unlucky" from "impossible".

The draw is a bipartite matching

Put the givers in one column and the receivers in another. Draw an edge from giver g to receiver r whenever allowed[g][r]. A valid Secret Santa draw picks one edge per giver so that every receiver is used exactly once. In graph terms, that's a perfect matching in a bipartite graph.

Finding a perfect matching is a solved problem. The augmenting-path algorithm, often called Kuhn's algorithm (a simpler relative of his 1955 Hungarian method), is about 20 lines: for each giver, try their candidates; if a candidate is already taken, try to move that receiver's current giver somewhere else, recursively.

const matchingDraw = (n: number, allowed: boolean[][], rng: Rng): number[] | null => {
  const receiverOf = new Array<number>(n).fill(-1);
  const giverOf = new Array<number>(n).fill(-1);
  const ids = Array.from({ length: n }, (_, i) => i);
  const candidates = ids.map((g) => shuffle(ids.filter((r) => allowed[g][r]), rng));

  const tryGiver = (g: number, seen: boolean[]): boolean => {
    for (const r of candidates[g]) {
      if (seen[r]) continue;
      seen[r] = true;
      // r is free, or r's current giver can be moved somewhere else
      if (giverOf[r] === -1 || tryGiver(giverOf[r], seen)) {
        giverOf[r] = g;
        receiverOf[g] = r;
        return true;
      }
    }
    return false;
  };

  for (const g of shuffle(ids, rng)) {
    if (!tryGiver(g, new Array<boolean>(n).fill(false))) return null; // provably impossible
  }
  return receiverOf;
};

Two things make it useful here:

1. It proves impossibility. If some giver can't be matched even after every augmenting path has been tried, no valid draw exists. The function returns null, and the page asks the organiser to remove a rule or add a person. It never times out. Note that "impossible" doesn't need anyone to have zero options: with 4 people and exclusions 0–1, 0–3 and 1–3, persons 0, 1 and 3 can each only draw person 2. Everyone has a candidate, yet three givers are competing for one receiver, so there's no valid draw. (That's Hall's marriage theorem: what matters is whether every group of givers has enough receivers between them.)
2. It's fast. Our generator caps groups at 50 people. Kuhn's algorithm is O(V·E), so even the worst case at that size is around a hundred thousand edge checks: a few milliseconds.

Shuffling each giver's candidate list, and the order in which givers are matched, keeps the result random.

The honest trade-off: random isn't the same as uniform

The matching result is random, but in general it's not uniform. Some valid draws come out more often than others, because the order the search runs in shapes which matching it finds first. Run it on 4 people with no exclusions and, of the 9 derangements, three come out about 8.7% of the time each and six come out about 12.3% each, where a fair draw would give 11.1%. Rejection sampling, by contrast, is uniform over the valid draws.

Why not sample a matching uniformly directly? Finding one is easy; counting them is computing a matrix permanent, which is #P-hard. Exact uniform sampling under arbitrary rules is the expensive part, so we only fall back to the fast, slightly uneven method when the cheap exact one runs out of luck.

So the generator uses both:

const SHUFFLE_TRIES = 500;

export const drawSecretSanta = (n: number, exclusions: readonly Exclusion[], rng: Rng) => {
  if (n < 2) return null;
  const allowed = allowedMatrix(n, exclusions);
  const ids = Array.from({ length: n }, (_, i) => i);

  for (let t = 0; t < SHUFFLE_TRIES; t++) {
    const perm = shuffle(ids, rng);
    if (perm.every((receiver, giver) => allowed[giver][receiver])) return perm;
  }
  return matchingDraw(n, allowed, rng); // the Kuhn code above
};

How often does it fall through to matching?

• No exclusions: each try fails about 63% of the time, so 500 failures in a row is less than 1 in 10^88 at any group size. In practice, ordinary draws always come from rejection sampling.
• 4 couples: 500 failures in a row is about 1 in 10^27.
• Two teams of 4 (1.4% valid): about 1 time in 1,300 the draw falls through to matching. Here symmetry happens to keep even the fallback uniform (every receiver on a team looks the same to the algorithm), but with lopsided rules it wouldn't be.
• Impossible rules: 500 quick shuffles, then matching returns null.

Ordinary groups get a uniform draw. Groups with heavy rules still get a quick random draw, and impossible rules get a clear error instead of a frozen tab.

Testing randomness without flaky tests

Pass the random source in instead of calling Math.random() inside. On the page it's backed by crypto.getRandomValues, and in tests it's a small seeded generator such as mulberry32, so every run is reproducible. The tests then check:

• Exclusions hold in both directions, across many seeded draws.
• A forced answer is found. With 4 people and exclusions 0–2, 1–3, 0–3 and 1–2, the only valid draw is [1, 0, 3, 2], and the function must return exactly that.
• Impossible means null. Three people with [[0, 1], [0, 2]] returns null, not a hang.
• Uniformity, roughly. Three people have exactly two derangements, [1, 2, 0] and [2, 0, 1]. Over 4,000 seeded draws, each must land between 46% and 54%.

The last test is coarse on purpose. It doesn't prove uniformity; it catches common shuffle bugs, such as the naive shuffle that picks j from the whole array at every step, which skews three people to about 44/56. It can't catch everything: the classic rng() * i off-by-one (Sattolo's algorithm) only produces single loops, and for three people both derangements are single loops, so it passes. A check that 4-person draws sometimes contain mutual pairs would catch that one.

Try it

If you want to see it working, our free Secret Santa generator runs this draw in your browser. It has no sign-up, takes exclusions for couples, and gives each person a link that carries their own match and nobody else's.

The takeaways if you build your own:

• Draw the whole assignment, not one person at a time.
• Shuffle and reject for a uniform draw when valid draws are common.
• Fall back to bipartite matching when they're rare, and let it tell you when there's no valid draw.
• Take the random source as a parameter, so your tests can be seeded.