Prove a Secret Santa Draw Is Possible with Matching

ملخص

Pixel shares a guide to modeling Secret Santa assignments as a matching problem, with givers and recipients represented as separate sets. It explains how to remove forbidden pairings, catch givers with no valid recipients, and detect whether complex rules make a draw impossible before invitations go out.

DEV Community

How to Prove a Secret Santa Draw Is Possible Before Sending Invitations

A Secret Santa draw gets difficult as soon as the rules become realistic. Maybe partners should not draw each other. Maybe nobody should receive the same person as last year. A manager should not draw a direct report. Two people share an address. One participant cannot ship internationally. The usual implementation is: shuffle the names, reject invalid results, and try again. That works for simple groups, but it cannot answer the organizer's most important question: Is this rule set possible at all? A loop that has failed 10,000 times may be unlucky, inefficient, or trapped in an impossible set of constraints. Those are very different situations. This post shows how to model the draw as a matching problem, detect impossible inputs early, and give an organizer a useful error instead of spinning forever. 1. Treat givers and recipients as two separate sets Create two copies of the participant list: the left side contains every giver; the right side contains every possible recipient; an edge means that giver is allowed to receive that person. Remove the self-edge for every person. Then remove every excluded pair. An exclusion is directional. If Ava must not draw Ben, remove Ava -> Ben. If the household rule works both ways, also remove Ben -> Ava. This detail prevents a common bug: storing a couple as one pair, then enforcing the rule in only one direction. 2. Reject locally impossible rows first Before running a full algorithm, check every giver's allowed-recipient list. for (const giver of participants) {
const allowed = participants.filter((recipient) =>
recipient !== giver && !blocked.has(${giver}\0${recipient})
);

if (allowed.length === 0) {
throw new Error(No allowed recipient remains for ${giver});
}
}
This catches obvious failures and produces a precise message. But it is not sufficient. For example, three different givers might each have only the same one recipient available. Every individual row is non-empty, yet a complete one-to-one draw is impossible. 3. Find a complete matching The right test is whether the bipartite graph has a matching that covers every giver. For small holiday groups, an augmenting-path matcher is plenty fast: function assign(giver, seenRecipients) {
for (const recipient of candidates.get(giver)) {
if (seenRecipients.has(recipient)) continue;
seenRecipients.add(recipient);

const previousGiver = recipientToGiver.get(recipient);
if (!previousGiver || assign(previousGiver, seenRecipients)) {
  recipientToGiver.set(recipient, giver);
  return true;
}

}
return false;
}
Call assign once for every giver. If any call fails, the complete rule set has no solution. Randomize each candidate list before matching if you want different valid draws. For reproducible testing, use a seed. 4. Validate the input before matching A production draw should reject: fewer than two participants; blank names; duplicate display names; exclusions containing unknown names; malformed exclusion pairs; a participant whose allowed-recipient list is empty; a full graph that cannot produce a complete matching. Duplicate names deserve special attention. Two different people called “Sam” are not the same participant. Use stable internal IDs even if the UI shows friendly names. 5. Keep privacy and recovery in the organizer workflow The algorithm is only one part of a reliable exchange. Before sending assignments, the organizer should also decide: whether exclusions are one-way or two-way; what happens if someone leaves after the draw; what minimum delivery information is required; who can see the private rule list; whether last year's assignments should be excluded; how to handle a late or missing gift without exposing every pairing. For a remote team, add time zones, country-specific shipping limits, and a fallback digital gift. I put the matching code and a practical organizer checklist in an open-source, dependency-free repository: Secret Santa Organizer Toolkit. If you wa...
Prove a Secret Santa Draw Is Possible with Matching
Powered by Readybot.io

الأحدث من Pixel

Incident Response: Look Beyond the Red Alert

Pixel’s DEV Community announcement explores how teams can fixate on one failing service while overlooking the real cause of an outage, such as a full …

Sach: AI Fact-Checks WhatsApp Forwards in India

Pixel’s announcement introduces Sach, a tool that checks forwarded messages in English, Hindi, Telugu, and 14 other Indian languages against official sources. It gives cited …

Java 25 Removes SecurityManager: What to Fix

Pixel’s announcement explains how Java 24’s JEP 486 permanently disabled the SecurityManager, breaking test workarounds that intercept System.exit. It recommends returning exit codes or throwing …

Why a Java HPA Got Stuck at 20 Kubernetes Pods

Pixel shares how a Spring Boot pricing service autoscaled to 20 Kubernetes pods and stayed there because the JVM retained committed heap memory after traffic …