A fair Secret Santa draw with exclusions is a matching problem

本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

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: Is a draw possible at all with these rules, and if not, why not, in words a person can act on? How do you pick one so that every valid draw is equally likely? How many valid draws are there? It turns out people like knowing.

“秘密圣诞老人”抽签看起来像是一次洗牌。但只要有人说“安娜和本是一对，他们不能抽到对方”或者“没人能抽到去年抽到的人”，它就不再是简单的洗牌了。我在 Toggle9 上构建了“秘密圣诞老人”生成器，并最终在其中发现了三个小问题：在这些规则下，抽签是否可行？如果不可行，原因是什么（且必须用人类可理解的语言表达）？如何选择才能确保每种有效的抽签结果概率均等？一共有多少种有效的抽签方式？事实证明，人们很想知道这些答案。

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.

所有这些都是基于 0/1 矩阵的纯函数，不涉及 DOM 操作，且随机性通过参数传入，以便测试时可以设置种子。模型如下：当且仅当第 i 个人可以为第 j 个人购买礼物时，“允许”矩阵 A[i][j] 为真。初始状态下，除了自己以外的所有人都是允许的，然后根据排除规则和去年的配对情况关闭相应的选项。

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.)

抽签本质上是一个排列，要求对于每个人，A[i][to[i]] 必须成立。在没有额外规则的情况下，这是一个错排问题：即没有不动点的排列。对于 6 个人，在 720 种全排列中有 265 种错排，占比约 36.8%。（该比例趋向于 1/e，这就是为什么对于小群体，“不断洗牌直到没人抽到自己”的方法行之有效。）

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.
是否可行？匹配问题，以及用于解释原因的霍尔定理（Hall’s theorem）。是否存在有效的抽签结果是一个二分图匹配问题：赠送者在一侧，接收者在另一侧，A 矩阵中允许的配对即为边。库恩（Kuhn）的增广路径算法可以在几行代码内给出答案。更有趣的是当算法失败时该如何反馈。“没有有效的抽签结果”对组织者来说毫无用处。霍尔定理指出，当且仅当某一组 k 个赠送者只能对应少于 k 个接收者时，完美匹配才不存在。
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.
公平选择：拒绝采样。一种诱人的方法是逐个分配，为每个人随机选择一个允许的接收者，并在遇到死胡同时回溯。这种方法能快速找到结果，但并不均匀：早期赠送者的选择会影响后续赠送者的可选范围，导致某些有效抽签结果出现的概率更高。最简单且最公平的方法也是最古老的方法：洗牌（Fisher–Yates 算法），根据规则检查，如果失败则重试。
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).
统计抽签结果。显示“共有 116 种可能的抽签方式”虽然是件小事，但能让人们确信规则并没有把抽签结果锁死。统计方法取决于变体：普通抽签中，完美匹配的数量即为矩阵 A 的积和式（permanent）。使用带有格雷码遍历的 Ryser 公式可以在 O(2ⁿ·n) 时间内计算出来。当人数超过 13 人时，中间项会超出双精度浮点数的精确范围，因此更大规模的群体会切换到 BigInt（最终计数结果依然在 Number 类型可表示的范围内）。