排列置换与720种可能性

Part 0. 引入：720个圆与置换的表示法

季节在铺沙的花园里轮转，同样的星辰为同样的人回环。
el giro de las estaciones en el jardín enarenado, la vuelta de los mismos astros para los otros mismos hombres.
胡里奥·科塔萨尔 《720个圆》
Julio Cortázar 720 Círculos

胡里奥·科塔萨尔在诗歌《720个圆》的开头这样写道：

“ 这首诗既是循环的，又是开放的。像洗牌一样重排诗节，就会生成不同的组合；而每一种组合，又都能从任何一个诗节开始读起。”

他将这首诗称之为 “置换诗歌”（poesía permutante）。诗不再是一个写定的顺序，而是一组可以被置换的节；置换一次，就是一首新的诗。读者通过将诗节自由排列，与诗人共同参与诗歌创作的过程。

将 $6$ 个互不相同的诗节排列，总共可以组成

$$ 6! = 6\times 5\times 4\times 3\times 2\times 1 = 720 $$

首不同的诗歌.

这样的计算告诉了我们 $720$ 种读法的存在，却无法叙述每一种读法下，我们如何阅读的具体过程.

于是我们将 $6$ 个诗节，根据排版时的初始顺序，分别编号为 $1,2,3,4,5,6$. 记 $\sigma(x)=a$ 为：新排列的第 $x$ 个位置上，放的是原编号为 $a$ 的诗节. 那么如果我们按排版逆序阅读这首诗，就可以将这种诗节的排列方式形式化地表示为

$\sigma(1)=6, \sigma(2)=5, \sigma(3)=4, \sigma(4)=3, \sigma(5)=2, \sigma(6)=1.$

这样“把每个位置重新指派给某个诗节”的行为，在数学上称为置换. 而诗歌的 $720$ 种读法，就可以这样表示为 $720$ 种置换.

我们也可以将刚刚那样按排版逆序的读法记作

$$ \sigma= \begin{pmatrix} 1&2&3&4&5&6\\ 6&5&4&3&2&1 \end{pmatrix} $$

这种置换的表示法我们称之为双行记号.

如果双行记号的行首默认按自然顺序书写，省略行首后，置换可以被表示为：

$\sigma=\sigma(1)\sigma(2)⋯\sigma(𝑛).$

我们称之为单行记号.

前文的例子利用单行记号可以写作 $\sigma=654321$.

在继续引入新的表示法前，我们需要先留意一下刚刚“诗节重排”的过程中，出现的一个自然而优美的性质：每个位置上都恰好放了一个诗节，而每个诗节也恰好只出现在一个位置上.

有没有觉得熟悉？

对了！双射！

而且通过诗节编号与位置的一一对应，我们可以使之成为是两个相同集合之间的双射！

即映射 $f:A→A$ 满足为双射.

我们把映射想象成一张以元素为节点、映射关系为有向边的图. 由双射的性质可知，每个节点的入度与出度均为 $1$，即对于每个节点，均有且仅有一条边指向它，由它发出的有向边也有其仅有一条. 这样就保证了，如果我们从任意一个节点开始，沿有向边一直走下去，所遍历的一定是一个环路 (若出现链路或环上有分支，则必然存在节点出度或入度不为 $1$ ). 那么这张映射的图，一定是由一个或多个互不相交的环路组成的（如果出现一个由自己指向自己的孤立节点，我们也视其为长度为 $1$ 的有向环）.

回到“诗节重排”问题，我们可以考虑这样一种表示排列的方法：

已知1号位置为6号诗节，那么6号位置一定是被其它诗节所占据. 于是我们找6号位置的诗节，发现恰好为1号诗节. 那么在这个重排中，1号与6号的位置是互换的. 然后继续考虑其它未被考虑过的诗节，确定它们所在的环路，就可以由

$\sigma=654321$

得到

$\sigma=(61)(52)(43)$.

同一个括号内的元素，处于同一个置换环内. 由前文双射的性质可知，每一个元素所处于的环有且仅有一个. 每个置换环内，在一次重排后均相当于进行了一次轮换.

什么是轮换
轮换是一种特殊的置换，其中所有的元素处于同一个置换环内。即若把置换所对应的映射关系如前文所述画成有向图，所形成的图由一个闭合的大有向环组成.
$\sigma=312$ 是轮换的例子之一. 我们也可以利用双行表示法更直观地展现该轮换中的环路：
$$\sigma=\begin{pmatrix}1&3&2\\3&2&1\end{pmatrix}$$
第一行仍为位置序号，第二行为诗节序号，但是这次我们把每一列的诗节序号作为下一列的位置序号. 可以发现，第 $n$ 列的诗节序号与第一列的位置序号相同，形成回路.
长度为 $k$ 的轮换也称作 $k$ - 轮换
$\sigma=312$ 为 $3$ - 轮换
$2$ - 轮换也被称为对换
$1$ - 轮换是置换中的 不动点

这样把置换拆成多个轮换的复合的表示法称为置换的轮换表示.

轮换表示中的不动点可以省略. 但如果置换是恒等变换，即所有轮换长度都是一，常常记作 $(1)$ 而非全部省略．

一个更复杂的轮换表示例子：

$\sigma=265431$ 等价于 $\sigma=(126)(35)$.

置换环的拆解唯一，但是轮换表示并不唯一，所以也可以记作 $\sigma=(261)(53)$、$\sigma=(612)(35)$ 等等. 读者可以自行推理.

//置换的轮换表示（置换环分解）
//复杂度：时间 O(n), 空间 O(n)

//cycle_cnt     置换环数量
//cycle_id      所属置换环的编号
//cycle_len     置换环长度
//p             某位置上置换后的编号

for (int i = 1; i <= n; ++i)
{
    if (cycle_id[i]) continue;    // 已属于某个环，跳过
    ++cycle_cnt;
    int j = i;
    while (!cycle_id[j])          // 沿置换走，直到回到已标记点
    {
        cycle_id[j] = cycle_cnt;
        ++cycle_len[cycle_cnt];
        j = p[j];
    }
}

Part 1. 加速！循环的路径与置换的叠加

⚠️ 阅前提示
此 part 着重进行算法练习总结，可能略过一些前面 part 未提及的知识
推荐根据个人需求结合 OI WIKI - 置换与排列食用
其余可供学习的参考资料列在了文末部分

1 . 1 任意对换排序与相邻交换排序

回顾：给定一个无序数列，通过相邻对换使之变为升序的最小操作次数等于逆序对数（每交换一组相邻的数，逆序对个数 +1 或 -1，最终要使逆序对个数为零）.

如果不限制相邻对换，而是可以取任意两数进行对换，则最小操作次数为 $元素数 - 置换环数$.

通过置换环性质可以证明.

如果将单次操作赋予不同的权重，可利用贪心处理（环内对换 / 合并环后跨环对换）.

顺带一提，置换环数与逆序对数奇偶性相同. 但置换环的处理是 $O(n)$ 的.

P1327 数列排序

P2091 排序

P2127 序列排序

1 . 2 置换的复合

有限集合上，所有置换均存在最小正整数 $a$ ：重复该置换 $a$ 次后，所有元素都回到原位. $a$ 为置换的阶.

于是可通过取模进行化简操作.

P5151 HKE与他的小朋友

1 . 3 置换的开根

单循环长度与指数互质，开根结果唯一；与指数不互质，无解.

P2227 洗牌机

1 . 4 对换所致的环的拆解与合并

对同一个环的两个不同元素进行对换操作，该环会被拆成两个环.

对不同环内的两个元素进行对换操作，两环会被合并为一个环.

P10454 奇数码问题

1 . 5 置换的计数问题

1 . 5 . 1 $n$ 个元素排成 $k$ 个环

第一类斯特林数： $n$ 个元素排 $k$ 个轮换.

递推式：

$$ {n \brack k} ={n-1 \brack k-1}+(n-1){n-1 \brack k} $$

$n$ 个元素的排列，对所有恰好包含 $k$ 个轮换的排列情况数进行加和，可得到排列情况总数：

$$ \sum_{k=0}^{n}{n \brack k} =\ n!\ . $$

第二类斯特林数： $n$ 个元素划分为 $k$ 个非空子集.

递推式：

$$ {n \brace k}={n-1 \brace k-1}+k{n-1 \brace k} $$

幂之间的转化

通常幂转换为下降幂 / 上升幂：

$$ x^n = \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} x^{\underline{k}} = \sum_{k} \left\{ \begin{matrix} n \\ k \end{matrix} \right\} (-1)^{n-k} x^{\overline{k}} $$

下降幂转换为通常幂：

$$ x^{\underline{n}} = \sum_{k} \left[ \begin{matrix} n \\ k \end{matrix} \right] (-1)^{n-k} x^k $$

上升幂转换为通常幂：

$$ x^{\overline{n}} = \sum_{k} \left[ \begin{matrix} n \\ k \end{matrix} \right] x^k $$

对偶性：

$$ \left[ \begin{matrix} n \\ k \end{matrix} \right] = \left\{ \begin{matrix} -k \\ -n \end{matrix} \right\}, \quad k, n \text{ 是整数}. $$

1 . 5 . 2 $k$ 个长度为 $L$ 的环拼接

设置换环 $X$ 长度为 $L$， $X^k$ 后生成 $gcd(k, L)$ 个长度为 $\frac{L}{gcd(k, L)}$ 的小环.
$k$ 个长度为 $L$ 的环拼接，有 $(gcd(k, L)-1)!\ \times \ \frac{L}{gcd(k, L)}^{gcd(k, L)-1}$ 种可能.

P11256 置换

参考资料

Julio Cortázar 720 Círculos

OI WIKI - 置换与排列

《潘震皓：置换群快速幂运算研究与探讨》

《具体数学》