排列变换

发表于 2023-01-30 更新于 2025-02-16 分类于算法竞赛

常见排列变换

我习惯将循环的顺序定义为正向，即循环 $1,2,3,4$ 对应的排列为 $2,3,4,1$。更加数学化的表达，$p$ 的循环 $a_1,a_2\cdots a_k$ 表示 $p_{a_1}=a_2,p_{a_2}=a_3\cdots p_{a_k}=a_1$。

定义一个排列 $p$ 的逆排列 $q$ 满足 $p_{q_i}=i$，通俗的讲，$q_i$ 表示 $p$ 中元素 $i$ 的位置，$q$ 一般记作 $p'$ 或 $p^{-1}$。

有性质 $p''=p$。证明是简单的，$p_{p'_i}=i,p'_{p''_i}=i$，所以 $p_{p'_{p''_i}}=p''_i$，又有 $p'_{p''_i}=i$，所以 $p_i=p''_i$。

在排列循环中，求逆的等价于将边反向，以上性质也就不证自明了。

定义两个排列的乘法 $c=a\cdot b,c_i=a_{b_i}$。

以置换的方式定义 $$ \[\begin{pmatrix}1,2\cdots n\\c_1,c_2\cdots c_n\end{pmatrix}\]

\[\begin{pmatrix}1,2\cdots n\\b_1,b_2\cdots b_n\end{pmatrix}\circ\] \[\begin{pmatrix}1,2\cdots n\\a_1,a_2\cdots a_n\end{pmatrix}\]

$$ $a\cdot b$ 等于 $a$ 左乘上置换 $b$。

如果是自乘，那么等价于循环的边移动若干次，$b$ 次幂就是将 $a_i$ 的边指向 $a_{((i+b-1)\bmod k) + 1}$

对于非自乘，我们研究它的运算律。

没有交换律
存在单位元 $e$ 满足 $a\cdot e=e\cdot a=a$。
存在结合律
- 置换的乘法运算存在结合律，被定义为左乘的排列乘法自然具有结合律。
- $a\cdot b\cdot c=c\circ(b\circ a)=(c\circ b)\circ a=a\cdot (b\cdot c)$
- 置换乘法的结合律描述为 $a\circ b\circ c=a\circ(b\circ c)$，证明是容易的，此处不再赘述。
存在逆元
- 一个置换 $\begin{pmatrix}1,2\cdots n\\a_1,a_2\cdots a_n\end{pmatrix}$ 的逆元显然为 $\begin{pmatrix}a_1,a_2\cdots a_n\\1,2\cdots n\end{pmatrix}$，也可以写成 $\begin{pmatrix}1,2\cdots n\\a'_1,a'_2\cdots a'_n\end{pmatrix}$
- 对于 $a$ 置换的逆元 $a'$，容易发现 $a''=a$，因此 $a'\circ a''=a'\circ a=e$
- 因此 $a\cdot b\cdot b^{-1}=a=b^{-1}\circ(b\circ a)=e\circ a=e\cdot a=a$