entscheidomat/posts/03-derangements-wichtel-algorithm-combinatorics.md

title, description, tags, canonical_url, target_keywords

title	description	tags	canonical_url	target_keywords
Derangements & Secret Santa: Solving the 1/e Fixed-Point Problem with Sattolo's Algorithm	The combinatorics of fixed-point free permutations (derangements) and how Sattolo's algorithm generates guaranteed non-self-matching Secret Santa assignment rings.	algorithms math typescript webdev	https://entscheidomat.com/ratgeber/lose-ziehen-online	lose ziehen online zettel ziehen online auslosungstool derangements algorithm sattolo algorithm

Derangements & Secret Santa: Solving the 1/e Fixed-Point Problem with Sattolo's Algorithm

Every year around the holidays or team events, millions of groups organize Secret Santa gift exchanges or anonymous partner matching. The core requirement is simple:

1. Every person gives exactly one gift.
2. Every person receives exactly one gift.
3. No person is assigned to give a gift to themselves.

However, groups that rely on physical paper drawing or naive online tools frequently hit a frustrating wall: someone draws their own name, forcing the group to throw all paper slips back into the hat and restart the entire process.

Why does this happen so frequently? In combinatorial mathematics, an assignment where no element remains in its original position is called a Derangement.

In this article, we will examine the mathematics behind derangements, prove why naive draw tools fail 63.2\% of the time (1 - 1/e), explore Sattolo's Algorithm, and implement a production TypeScript engine for automated, zero-failure Secret Santa draws.

---

1. The Mathematics of Derangements and Euler's Number e

In combinatorics, a derangement is a permutation of elements of a set in which no element appears in its original position. The number of derangements of a set of n elements is denoted by the subfactorial !n.

The Subfactorial Formula (!n)

The number of valid fixed-point-free permutations !n is given by:

!n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!} = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)

As n grows, the ratio of derangements !n to total permutations n! rapidly converges to:

\lim_{n \to \infty} \frac{!n}{n!} = \frac{1}{e} \approx 0.36787944 \dots

Where e \approx 2.71828 is Euler's number.

The 63.2% Failure Rate Paradox

This equation reveals a counter-intuitive mathematical truth:

\text{Probability of at least one self-draw} = 1 - \frac{!n}{n!} \approx 1 - \frac{1}{e} \approx 63.212\%

Whether your group has 5 participants, 12 participants, or 100 participants, in roughly 63.2% of all random draws, at least one person will draw their own name!

Group Size (n)	Total Permutations (n!)	Derangements (!n)	Success Rate (\%)	Failure Rate (\%)
n = 3	6	2	33.33%	66.67%
n = 4	24	9	37.50%	62.50%
n = 5	120	44	36.67%	63.33%
n = 10	3,628,800	1,334,961	36.79%	63.21%
n \to \infty	\infty	\infty / e	36.79% (1/e)	63.21% (1 - 1/e)

Relying on simple paper drawing or a basic Zufallsgenerator means you have less than a 37% chance of a clean first try.

---

2. Why Rejection Sampling Is Inefficient

A naive programmer might attempt to solve this using Rejection Sampling: generate random shuffles until one arrives with zero self-matches.

// ❌ INEFFICIENT: Rejection Sampling for Derangements
function naiveDerangement<T>(array: T[]): T[] {
  let attempt: T[];
  let isDerangement = false;

  while (!isDerangement) {
    attempt = shuffleArray(array);
    isDerangement = attempt.every((val, idx) => val !== array[idx]);
  }

  return attempt;
}

While rejection sampling works for small n, its expected number of attempts is \frac{1}{1/e} \approx e \approx 2.718 draws. Moreover, it cannot easily accommodate exclusion constraints (e.g. "Spouse A cannot give to Spouse B"). When strict constraints are added, the acceptance probability plummets near zero, causing infinite loops (O(\infty) time complexity).

---

3. Sattolo's Algorithm: Guaranteed Cyclic Derangements in O(N)

In 1986, Sandra Sattolo published a modified version of the Fisher-Yates shuffle algorithm. While Fisher-Yates generates all n! permutations uniformly, Sattolo's Algorithm generates only permutations consisting of a single cyclic ring of length n.

By forcing a single closed cycle (1 \to 3 \to 5 \to 2 \to 4 \to 1), Sattolo’s algorithm mathematically guarantees that no element ever maps to itself, achieving a derangement in a single O(N) pass.

The Algorithm Difference

• Fisher-Yates: Swaps index i with a random index j \in [0, i].
• Sattolo: Swaps index i with a random index j \in [0, i - 1] (excluding i itself!).

Because index i can never be swapped with itself, no fixed points can ever form.

---

4. TypeScript Implementation of Sattolo's Algorithm

Here is the TypeScript implementation for generating cyclic Secret Santa assignment rings:

export interface Assignment<T> {
  giver: T;
  receiver: T;
}

/**
 * Generates a guaranteed cyclic derangement using Sattolo's Algorithm.
 * Time Complexity: O(N) | Space Complexity: O(N)
 */
export function generateSattoloRing<T>(participants: readonly T[]): Assignment<T>[] {
  if (participants.length < 2) {
    throw new Error("At least 2 participants are required for a valid draw.");
  }

  const items = [...participants];
  const buffer = new Uint32Array(1);

  // Sattolo's loop: index i goes from N-1 down to 1
  for (let i = items.length - 1; i > 0; i--) {
    // Pick j in range [0, i - 1] -> EXCLUDES i!
    crypto.getRandomValues(buffer);
    const j = Math.floor((buffer[0] / (0xFFFFFFFF + 1)) * i);

    // Swap items[i] and items[j]
    const temp = items[i];
    items[i] = items[j];
    items[j] = temp;
  }

  // Convert cyclic array into Giver -> Receiver assignments
  const assignments: Assignment<T>[] = [];
  for (let idx = 0; idx < items.length; idx++) {
    const giver = items[idx];
    const receiver = items[(idx + 1) % items.length]; // Closed cyclic loop
    assignments.push({ giver, receiver });
  }

  return assignments;
}

Example Output for ['Alice', 'Bob', 'Charlie', 'Diana']:

Alice 🎁 ➔ Bob
Bob 🎁 ➔ Charlie
Charlie 🎁 ➔ Diana
Diana 🎁 ➔ Alice

Guaranteed zero self-matches, generated in a single O(N) execution.

---

5. Advanced Exclusion Rules (Constraint Satisfaction)

What if certain participants cannot draw each other (e.g. couples, managers and direct reports)?

When exclusion matrices are introduced, pure Sattolo cycling may violate constraints. The optimal solution is a Backtracking Constraint Solver:

export interface Person {
  id: string;
  name: string;
  excludeIds: string[]; // Partner/Family exclusion list
}

export function solveConstrainedSecretSanta(people: Person[]): Assignment<Person>[] | null {
  const givers = [...people];
  const receivers = [...people];
  const assignments: Assignment<Person>[] = [];

  function backtrack(index: number): boolean {
    if (index === givers.length) return true;

    const giver = givers[index];

    for (let r = 0; r < receivers.length; r++) {
      const candidate = receivers[r];

      // Validation Checks
      if (candidate.id === giver.id) continue; // No self-draw
      if (giver.excludeIds.includes(candidate.id)) continue; // Exclusion constraint

      // Place assignment
      assignments.push({ giver, receiver: candidate });
      receivers.splice(r, 1); // Remove candidate temporarily

      if (backtrack(index + 1)) return true;

      // Backtrack if path fails
      receivers.splice(r, 0, candidate);
      assignments.pop();
    }

    return false;
  }

  const success = backtrack(0);
  return success ? assignments : null;
}

---

Summary & Key Takeaways

1. The 1/e Rule: In any naive random raffle or drawing, there is a 63.2% chance that at least one person draws themselves.
2. Sattolo's Algorithm modifies Fisher-Yates by picking random swap indices j \in [0, i-1], producing a guaranteed derangement in O(N) time.
3. For custom exclusion rules (e.g. couples), use a Backtracking Constraint Solver.

To try out an online draw tool that handles participant lists, exclusions, and fair draws without registration, visit Entscheidomat Lose Ziehen Online.

---

FAQ (Schema Structured Data)

{
  "@context": "https://schema.org",
  "@type": "FAQPage",
  "mainEntity": [
    {
      "@type": "Question",
      "name": "What is a derangement in mathematics?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "A derangement is a permutation of a set of items where no element remains in its original position (zero fixed points)."
      }
    },
    {
      "@type": "Question",
      "name": "Why do people draw themselves in Secret Santa?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "Because in naive random draws, the probability of at least one self-match is 1 - 1/e, which equals approximately 63.2% regardless of group size."
      }
    },
    {
      "@type": "Question",
      "name": "How does Sattolo's Algorithm work?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "Sattolo's algorithm modifies Fisher-Yates by swapping element i with a random element j from index 0 to i-1, guaranteeing a single cyclic permutation with zero fixed points."
      }
    }
  ]
}