A fair Secret Santa draw with exclusions is a matching problem

A Secret Santa draw involves assigning each person a recipient, with certain exclusions to consider. It starts as a simple shuffle, but exclusions and past draws complicate the process. The author built a Secret Santa generator that determines if a valid draw is possible, how to pick one uniformly at random, and how many valid draws exist. This process relies on functions operating on a 0/1 matrix with random input for testing purposes.

The allowed matrix, A[i][j], indicates if person i can buy for person j, excluding oneself, current partners, and previous year's matches. A valid draw is a permutation where A[i][to[i]] is true for every person. Without additional rules, this is a derangement, or a permutation with no fixed points. For six people, there are 265 such permutations out of 720 possible shuffles, roughly 36.8%.

The first challenge is determining if a valid draw is possible at all. This is a bipartite matching problem, represented by a graph where givers and receivers are on opposite sides, and edges connect allowed pairs. Kuhn's augmenting-path algorithm can find a perfect matching in just a few lines, answering if a draw exists and, if not, why not. The failing groups reveal which exclusions prevent a solution.

Beyond existence, the second challenge is picking a draw uniformly at random among all valid options. Simple rejection sampling, like shuffling and checking against rules, works but doesn't give each valid draw equal probability. Backtracking during selection introduces bias, skewing certain draws more than others. The author's solution is to shuffle the list of potential assignments repeatedly until a valid draw emerges, ensuring every possible outcome has an equal chance of being chosen.