第十四章真的抽一次

祺乐已经证明，仙人掌图上一定有好的共同安排。可数学上说“存在一种共同安排”，还没有告诉我们怎样在电脑上方便地把它抽出来。仙人掌图上的抽签，是瀚林接下的活。

不存大表格

如果每个顶点有 $s$ 种回答，一条边的最大耦合是一张 $s$ 行 $s$ 列的表。$s$ 一大，表就很大，边一多，就要存很多张大表。能不能不存？

瀚林拿这个问题问过 AI，回复里给的是一种“照抄或补抽”的抽法。瀚林没有直接拿来用，先拿标准签盒算了一遍。

还是第六章那一步删除。删前是标准签盒，两条都在：电影院 $5$ 张，公园 $3$ 张，图书馆 $2$ 张。删掉电影约定以后，是只剩怕吵的那一盒：电影院 $2$ 张，公园 $5$ 张，图书馆 $3$ 张。照抄或补抽，说成故事是这样：

• 删前抽到电影院：以 $\frac{2}{5}$ 的机会照旧去电影院；否则改去公园或图书馆，公园占 $\frac{2}{3}$，图书馆占 $\frac{1}{3}$。
• 删前抽到公园或图书馆：一定照旧。

换走的全是原来的电影院，和第六章那张最好的签表一样。整个过程只看两个签盒，用不着那张三行三列的签表。

去掉名字，一般的规则是这样。看一条边，父顶点的表是 $p$，子顶点的表是 $q$。对每种回答 $a$，记两边共同能保留的部分为 $r(a)$，也就是 $p(a)$ 和 $q(a)$ 中较小的那个。抽法是：

父顶点已经抽到了回答 $a$。那么子顶点以 $\frac{r(a)}{p(a)}$ 的机会照抄 $a$；否则，从 $q$ 减去 $r$ 剩下的那部分里，按比例抽一个回答。

在上面的例子里，甲、乙、丙就是电影院、公园、图书馆。共同部分 $r$ 是甲 $\frac{2}{10}$、乙 $\frac{3}{10}$、丙 $\frac{2}{10}$；$q$ 减去 $r$ 剩下乙 $\frac{2}{10}$、丙 $\frac{1}{10}$，按比例就是乙 $\frac{2}{3}$、丙 $\frac{1}{3}$。父顶点是甲时，照抄的机会是 $\frac{2/10}{5/10}=\frac{2}{5}$；是乙或丙时，$r$ 和 $p$ 一样大，照抄的机会是 $1$。

为什么一般也对？父顶点是 $a$ 的机会是 $p(a)$，再乘照抄的机会 $\frac{r(a)}{p(a)}$，正好留下 $r(a)$；不照抄的机会加起来正好是全变差距离，剩下的部分按 $q$ 多出来的比例补齐，子顶点每种回答的机会就正好是 $q$。整个过程只需要记住几串长度为 $s$ 的数，不需要 $s\times s$ 的大表。抽一次完整的签要算多少步，放在附录三“需要多少计算”一节。

圈和接缝

对一个圈，先按祺乐的平衡式随机决定拿掉哪条边，再沿剩下的路一个一个往下抽。对仙人掌图，就沿着块和割点一块一块地处理。

一个新的圈接到已经抽好的割点 $O$ 上时，$O$ 的回答已经定了。这时还能按原来的机会决定拿掉哪条边吗？会不会因为已经知道了 $O$ 的回答，拿掉各条边的机会就该变？

不会。无论拿掉哪条边，沿路做最大耦合时，$O$ 的边际分布都是同一张表。所以“拿掉哪条边”和“$O$ 回答什么”互不影响，知道了 $O$ 的回答，拿掉各条边的机会还是原来的那些。

同一张签要反复用

第七章说过，所有保留情况共用同一张签：先删电影还是先删怕吵，终点都是“两条都删”，读的是同一栏。落到程序上，就是：抽好的一张完整的签要保存下来反复用，或者，从随机种子到整张签的那个过程每次都完全一样。如果每次访问都重新按条件抽一遍，即使每次的分布都对，实际的回答也可能变来变去，“不管走哪条路线，终点都读到同一个回答”的承诺就落空了。

韵吉问：“那这张答案单存在哪儿？”

“存在一个文件里。”瀚林说，“删记录的时候，这个文件不能删。”

文件里只有一排去处，第几种情况就读第几栏。被删的那条记录本身不在文件里，不过“两条都在”那几栏的去处，是照着它抽出来的。

这一部求出来的数，也填上了记分牌。只能按撤销的顺序删的时候，情况排成一条链，倍数是 $1$，每一步都能做到单独最好。两条记录先删哪条随你，情况排成正方形，倍数是 $\frac{3}{2}$，最坏的那一步多付一半。三角形、五边形这些圈不是删记录得来的，它们的数说明，最坏情况下圈越长越难，但都到不了 $2$。