置换的轮 / Permutation Cycle

一句话

把 $n$ 个东西重新排一遍，就得到一个置换。从任何一个位置出发，反复问”原来在这儿的东西去哪了”，你一定会回到出发点——走过的这条闭合链条叫一个轮。

一个麻烦

三十个人参加交换礼物。规则是每个人把自己带来的礼物交出去，最后每个人拿到一份别人的。

散场后你发现，你想要的那份礼物——小李带来的那个——不在你手上。你手上是小王的。

你想找到小李的礼物在谁那儿。可你唯一知道的信息是：你手上这份是谁带来的。

一个笨办法：去问三十个人，“你手上那份是谁带来的？“问到有人回答”小李”就找到了。平均要问十五个人，最坏要问三十个。

但你手上还有一条没用上的线索。你拿的是小王的礼物——那么小王呢？去问小王，他手上是谁的？假设是小张的。再去问小张。这样一路走下去，会发生一件事：你迟早会走到某个人，他手上拿的是你带来的礼物。

到这一步链条闭合了。而在这条链条上你一路记下了”谁拿着谁的”——如果小李在这条链上，你在路过时就已经知道答案了。

几个朴素猜测

猜测一：链条会不会走进死胡同，或者原地打转？

不会，而这一点值得停下来想清楚。

每个人交出恰好一份、收到恰好一份。所以”你手上的礼物属于谁”这个映射是一一对应的：没有两个人拿着同一个人的礼物（每人只带了一份），也没有谁的礼物没人拿（都发出去了）。

正因为一一对应，链条不可能岔成两条，也不可能撞进一个已经访问过的中间位置——如果链条走到某个已访问的人身上，那个人就会有两个”前任”，也就是两份礼物被同一个人带来，矛盾。所以它唯一的收场方式是回到起点。人数有限，所以它必须收场。

猜测二：那一条链会不会串起所有人？

不一定。三十个人可能构成一个长度 30 的大轮，也可能是十五对两两互换——那就是十五个长度 2 的小轮。

这正是关键的不确定性：跟着链条走，你只会走遍自己所在的那个轮。小李如果在另一个轮里，走完自己这圈也遇不上他。

猜测三：那这个办法到底比挨个问强在哪？

强在它把”一次问话”的信息量用满了。挨个问，每一次得到的答案要么是”是”要么是”不是”，失败的那次基本什么也没留下。跟着链条走，每一步都同时做两件事：检查这个人是不是小李，并且给出下一个该问谁。

代价是它只覆盖一个轮。所以真正的做法是两者结合：走完一个轮，如果没找到，从任意一个还没走过的人重新起一条链。

机制

写成记号会清楚很多。设 $\sigma$ 是那个置换：$\sigma(i)$ 表示 $i$ 号位置上的东西原本属于谁。

从 $i$ 出发反复施加 $\sigma$：

   i  ->  σ(i)  ->  σ(σ(i))  ->  ...  ->  i

一定存在某个 $k \ge 1$ 使 $\sigma^k(i) = i$，这个最小的 $k$ 就是 $i$ 所在轮的长度。

一个具体例子，$n = 6$：

   位置   1   2   3   4   5   6
   σ      3   5   1   4   2   6

   从 1 出发：  1 -> 3 -> 1              轮长 2
   从 2 出发：  2 -> 5 -> 2              轮长 2
   4 和 6 各自不动                       轮长 1 (两个不动点)

这个 $\sigma$ 分解成四个轮：$(1\,3)(2\,5)(4)(6)$。任何置换都能这样唯一地分解成不相交的轮。

轮长的分布决定了”跟着链条走”要付多少代价。对一个均匀随机的置换，有个漂亮的结果：从任意固定起点出发所在的轮，其长度在 $1$ 到 $n$ 上是均匀分布的。于是期望轮长是

$\mathbb{E}[k] = \frac{1+2+\cdots+n}{n} = \frac{n+1}{2}$

而只有一部分元素被打乱、其余不动时（比如只把 $m$ 个位置互相打乱），链条只在这 $m$ 个里面绕，期望长度按 $m$ 算而不是 $n$。这是个很实用的差别：局部扰动的追查成本只跟被扰动的规模有关，跟系统总规模无关。

为什么值得知道

这个结构在一个地方反复出现：某个你依赖的映射被悄悄改过了，而你手里还留着旧版本。

旧映射不是垃圾。旧映射加上”东西只是换了位置、没有消失”这个前提，等于一张可以推理的地图。挨个重试是把旧信息当垃圾扔了；跟着轮走是把它当地图用。

两者的成本差可以很大。$m$ 个位置被打乱，挨个试的期望次数是 $O(m)$ 且每次都要付一次完整的试探代价；跟着轮走的期望步数是 $(m+1)/2$，但每一步都在缩小范围，而且走到就是答案，不需要验证别的可能。

现实里的形态：一个缓存的键被重新分片、一批文件被批量改名、一个 API 的字段被换过位置、一个工具集的名字被重排。第一反应通常是”我的信息过期了，重新探一遍”。往往更快的是问一句：旧的那份还能当地图用吗？

收束

回到那三十个人。你手上拿着小王的礼物，这个事实看起来只是”我没拿到想要的”——一条关于失败的信息。

但它同时是一个指针：它指向小王。而小王手上那份又指向下一个人。你抱怨的那条信息本身就是路。

多数时候人们没有沿着链条走，不是因为算不出来，是因为没意识到手里那份”过期的”东西还有指向性。