置换群与魔方

· · 算法·理论

首先考虑一个排列 p=\{ 1,2, \dots n \}(n > 1)，定义一次操作为交换排列中任意两个不同的元素。

对于初始排列做偶数次操作，可以得到若干排列的集合 S_1；做奇数次操作，可以得到若干排列的集合 S_2。

我们发现，S_1 与 S_2 不交，且 |S_1|=|S_2|。

换句话说，如果我们把操作偶数次后的排列称作偶排列，则一个偶排列只能由偶数次操作得到，而不可能通过奇数次得到。

考虑一个排列 p 的逆序对个数为 c_p，初始 c_p=0。

进行一次操作之后，假设交换了 p_i 和 p_j(i<j)，若 p_i < p_j，发生变化的只可能是位于 [i+1,j-1] 之间且值域属于 [p_i+1, p_j-1] 的元素。而且这样的元素对于逆序对的贡献是 \pm 2。在那之后，由于 p_i < p_j，逆序对个数还会 +1。换句话说，逆序对个数的奇偶性发生了变化。

因此我们发现，根据一个序列的逆序对个数的奇偶性就可以看出它是奇排列还是偶排列。 换句话说，如果把每个排列看作一个点，对排列进行一次操作视作边（由于能交换回来，不妨视作无向边），则整张图是一个二分图。 ----- 然后考虑大小相等这件事。对于一个排列，我们可以建立一个映射，比如规定 $p$ 交换前两个元素 $p_1$，$p_2$ 得到 $p'$。容易发现，所有偶排列都可以映射到另外一个奇排列上，且是一一对应的。 ---- ## 置换 我们称一个置换是将一系列有顺序的元素重新排列。如 $p=\{1,2,3,4\}$ 可以将其重新排列成 $p'=\{1,3,2,4\}$，其实质是 $2$ 和 $3$ 换了位置，至于具体数字或字母表示是无关紧要的。只要置换的实质没变，那么两个置换就是一样的。 我们可以将其写作

\begin{pmatrix} 1 & 2 & 3 & 4 \ 1 & 3 & 2 & 4 \ \end{pmatrix}

，或等价表示为

\begin{pmatrix} 2 & 3 & 1 & 4 \ 3 & 2 & 1 & 4 \ \end{pmatrix}

我们可以将其等价地写为 cycle notation 的形式：$(1)(4)(2 ~~ 3)$，表示 $1$ 与 $4$ 位置不变，而括号中的元素轮换（依次变为后一位的元素）。 对于

\begin{pmatrix} 1 & 2 & 3 & 4 \ 1 & 4 & 2 & 3 \ \end{pmatrix}

置换里有几个元素，就称作几阶置换（如 $(1 ~~ 4 ~~ 3)$ 为三阶置换）。 对于先后操作几个置换或同一个置换，我们称为复合运算。 如果对某个置换 $(a~~b)$ 操作两次（写作 $(a~~b)^2$），显然元素归位不会变化。同理，$(x_1~~x_2 \dots x_k)^k$ 也不会产生变化。称其为恒等变换。 如果是不同的置换，比如先后进行 $(1~~4)(1~~3)$，可以看作 $1$ 投入了 $4$ 的盒子，$4$ 先投入了 $1$ 的盒子然后再转移到 $3$ 的盒子，最后 $3$ 被投到 $1$ 的盒子里。也就是 $(1~~4)(1~~3) = (1~~4~~3)$。 实际上，拓展可得 $(a~~b\dots z)=(a~~b)(a~~c)\dots(a~~z)$。这里我们将一个 $n$ 阶置换拆分成了 $n-1$ 个二阶置换。同样，对于多个高阶置换的复合，也可以拆成若干个二阶置换。特殊的，有时候也将二阶置换直接称作交换。 对于一个 $x$ 阶置换，如果拆成奇数个二阶置换（$x$ 为偶数），则为奇置换；否则为偶置换。 如果是多个置换拼在一起，判定也是一样的。 ---- 魔方即是置换群的一个子群。 以下讨论如果没有特别指代，一般是对**传统三阶魔方**进行讨论。 我们考虑魔方上的 $9 \times 6 =54$ 个小格： ![](https://cdn.luogu.com.cn/upload/image_hosting/cpmln5kl.png) 这里我们用字母来表示六个面。 考虑到其最小单位是独立的小格（面），为了方便，我们用两个或者三个字母来表示一个格子。比如 $\texttt{Df}$ 表示底面（D）靠近上面（F）的格子。对于每个面中心的格子，观察到任意转动后不会发生改变，故不考虑。 对于魔方的一次或多次连续转动，我们可以将其写成置换的形式。 例如，进行一次 $\texttt{UR}$ 操作（意思为先顶面顺时针转动 $90^\circ$，然后右面顺时针转动 $90^\circ$。转动表示详见 [Part 1](https://www.luogu.com.cn/article/yc1aq0gv)）， 将每个块的位置变化以置换的形式写出： $$ (\texttt{Uf} ~~ \texttt{Ul} ~~ \texttt{Ub} ~~ \texttt{Bl} ~~ \texttt{Dl} ~~ \texttt{Fl} ~~ \texttt{Ur}) (\texttt{Fu} ~~ \texttt{Lu} ~~ \texttt{Bu} ~~ \texttt{Rb} ~~ \texttt{Rd} ~~ \texttt{Rf} ~~ \texttt{Ru} ) (\texttt{Ufl} ~~ \texttt{Ubl} ~~ \texttt{Bdr} ~~ \texttt{Dfr} ~~ \texttt{Fur} ~~ \texttt{Luf} ~~ \texttt{Bul} ~~ \texttt{Rbd} ~~ \texttt{Rfd} ~~ \texttt{Rfu} ~~ \texttt{Ful} ~~ \texttt{Lub} ~~ \texttt{Drb} ~~ \texttt{Frd} ~~ \texttt{Urf}) (\texttt{Ubr} ~~ \texttt{Bur} ~~ \texttt{Rub}) $$ 这个操作本质上由两个 $7$ 阶置换、一个 $15$ 阶置换和一个 $3$ 阶置换组成。每做一次操作，可以看作每一个单独的置换（某些格子的排列）里的元素都向后跳了一步。 我们如果想知道，一个魔方重复多少次这样的操作可以恢复原状，可以计算所有单个置换阶数的 $\textrm{lcm}$（将其称作这个操作的阶数）。 对于这个 $\texttt{UR}$ 操作，恢复原状的操作次数即为 $\textrm{lcm} (7, 15, 3) = 105$（或 $210$ 次转动）。 另一方面我们也可以考虑，魔方在物理意义上由 $26$ 个方块组成。不考虑中心块的话，则由 $12$ 个棱块（共用两面）和 $8$ 个角块（共用三面）组成。 我们用两个或三个大写字母表示一个方块（如 $\texttt{UR}$ 表示连接顶面和右面的棱块）。对于某个旋转操作（例如 $\texttt{F}$）我们观察方块位置的置换： $$(\texttt{FU}~~\texttt{FR}~~\texttt{FD}~~\texttt{FL})(\texttt{FUR}~~\texttt{FDR} ~~ \texttt{FDL} ~~ \texttt{FUL})$$ 观察到这是一个偶置换（可以拆分成 $6$ 个二阶置换）。 根据置换的性质，通过多个旋转操作得到的方块位置的改变始终是偶置换，不可能出现奇置换。例如不存在某个公式只交换某两个棱块的位置（即产生 $(\texttt{UL} ~~ \texttt{UF})$ 这样的置换，因为这是一个奇置换）。 以方块为单位的表示方法相较于以面为单位，更加简洁，但不包含方块的方向信息（换个说法，方块的自身翻转）。例如前文中 $(\texttt{Ubr} ~~ \texttt{Bur} ~~ \texttt{Rub})$ 这种就无法表示。 关于方块的定向方法，详见 [Part 2](https://www.luogu.com.cn/article/yc1aq0gv)。 ## 交换子 如果了解了魔方的置换原理，理应可以通过一些操作构造一些基本置换（比如同时翻转两个块的方向，交换一些块的位置）来解决魔方。 接下来介绍交换子的思想。 如果我们已经知道一个操作可以同时翻转 $\texttt{UF}$ 和 $\texttt{UL}$ 两个棱块的方向，那么如何翻转 $\texttt{FD}$ 和 $\texttt{RD}$ 这两个棱块？ 自然地，我们会把魔方整体转 $180^\circ$，这样本来的底面 $\texttt{D}$ 就变成了顶面 $\texttt{U}$，同时本来的 $\texttt{FD}$ 和 $\texttt{RD}$ 两个块也放到了 $\texttt{UF}$ 和 $\texttt{UL}$ 的位置。此时我们再进行原来的操作，最后再把魔方整体转 $180^\circ$ 回去，这样就做成了翻转 $\texttt{FD}$ 和 $\texttt{RD}$ 的操作。 可以看出，其基本思想是，已知一个基本操作 $A$，如果可以通过一些别的操作 $B$（例如将魔方整体翻转 $180^\circ$）将的 $A$ 利用起来，那么我们就可以先做 $B$，然后做 $A$，最后再做 $B$ 的逆操作，即 $B A B^{-1}$。 群论中把这个称为 $A$ 对于 $B$ 的共轭，记为 $A^B = BAB^{-1}$。 ---- 如果现在我们需要翻转 $\texttt{UF}$ 和 $\texttt{UB}$ 块，可以先进行 $\texttt{BL}$ 操作（注意区分操作、块的位置以及块本身的表示），把 $\texttt{UB}$ 块转到 $\texttt{UL}$ 的位置，做上述公式，再把块转回来。此时在共轭中 $B=\texttt{BL}$。 或者，我们也可以先做一次翻转 $\texttt{UF}$ 和 $\texttt{UL}$ 的操作，然后将魔方（从上往下看）整体逆时针转 $90°$，随后做一次翻转 $\texttt{UF}$ 和 $\texttt{UL}$ 操作的逆操作（因为要把多翻转的那个方块翻转回来，同时也能翻转我们目标翻转的那个方块）。随后再将魔方整体转回来。 如果我们把魔方整体逆时针旋转 $90°$ 这个操作记为 $C$，则我们的一系列操作可以写成 $ACA^{-1}C^{-1}$。 这便是交换子。正式地说，对于两个操作 $A,B$，可以称操作 $ABA^{-1}B^{-1}$ 为一个交换子，记做 $[A,B]$。注意括号里 $A,B$ 的顺序一般是不可以交换的。 在个别情况下可以交换，例如 $[\texttt{L}, \texttt{R}]=[\texttt{R}, \texttt{L}]=e$，因为两个操作不互相影响。如果两个操作可交换，那么他们的交换子等于单位元。 通过交换子，我们容易构造一些魔方的公式。 eg. 构造上文中翻转 $\texttt{UL}$ 和 $\texttt{UF}$ 两块，其他方块都不改变的操作公式。 首先，我们可以简单地构造出顶面只翻转 $\texttt{UF}$ 块，不动其他块的操作。注意这里不考虑底下两层的情况，可以任意打乱，例如 $M=\texttt{L'RF2LR'D'L'RFLR'}$。 考察操作 $M$ 的效果： 对于顶面，翻转 $\texttt{UF}$ 块的方向。 对于下面两层，进行一个打乱。 再看 $M$ 的逆操作 $M^{-1}$ 的效果： 对于顶面，翻转 $\texttt{UF}$ 块的方向。 对于下面两层，还原 $M$ 造成的打乱。 如果先进行 $M$ 再进行 $M^{-1}$，显然魔方会被还原。 如果在进行了 $M$ 操作之后做一个旋转 $\texttt{U}$，此时原先 $\texttt{UF}$ 块的位置变成了 $\texttt{UL}$ 块。这个时候再进行 $M^{-1}$ 的操作，就会造成复原下面两层，并翻转 $\texttt{UF}$ 和 $\texttt{UL}$ 两块的效果。 :::info[习题] 利用交换子创造一个同时翻转两个相邻角块的公式。 ::: 进一步，考虑如何利用交换子来交换方块的位置。 在前文，我们已经得到了结论，方块不能进行奇置换。也就是说，像 $(\texttt{UFL}~~ \texttt{UFR})$ 这样的方块置换是不可行的。 但三个方块的置换是可行的，例如 $(\texttt{UBR}~~\texttt{UFR}~~\texttt{UFL})$ 这样的三阶置换是可以达成的。考虑怎么用交换子实现这样的三阶置换。 我们把三阶置换拆开，$(\texttt{UBR}~~\texttt{UFR}~~\texttt{UFL})=(\texttt{UFL}~~\texttt{UFR})(\texttt{UFR}~~\texttt{UBR})$，我们可以先不顾下面两层的混乱，做一个操作交换 $\texttt{UFL}$ 和 $\texttt{UFR}$ 这两个块，然后做一次 $\texttt{U}$ 操作，随后再做一次刚才操作的逆操作，下面两层的混乱就会被还原。最后做一次 $\texttt{U'}$ 操作，一个三阶置换就可以被达成。 ---- 现在系统考察交换子和置换的关系。 对于两个互不影响的操作，它们的交换子等于单位元，而如果两个操作交集很小，那么它们交换子的大小也比较小。 对于魔方来说，我们知道一个操作可以带来某些方块的置换。我们称这些所有被置换的方块称为这个操作的支集。操作 $A$ 的支集记做 $supp(A)$。 :::info[闲话] 在数学上，一个函数的支集被定义为，如果一个实值函数 $f:X\to R$，则 $supp(f)=\{ x \in X | f(x) \ne 0 \}$。可以思考一下这里的支集和置换的支集有什么关系。 :::: 接下来有一个关于交换子的比较重要的定理： 有两个操作 $A$ 和 $B$，若 $supp(A) \cap supp(B)$ 为单元素集，那么 $A,B$ 的交换子 $[A,B]$ 带来的方块置换为三置换。 比如说，接下来我们**只考虑所有的棱块**。观察到 $supp(\texttt{F}) \cap supp(\texttt{R'})$ 只有一个元素 $\texttt{FR}$，那么如果我们操作交换子 $[\texttt{F},\texttt{R'}]$ 即 $\texttt{FR'F'R}$，我们会发现只置换了 $\texttt{FR},\texttt{FU},\texttt{UR}$ 这三个方块。 对于角块，我们观察刚刚的交换子 $\texttt{FR'F'R}$，它的支集为 $\{ \texttt{UF},\texttt{UR},\texttt{FR},\texttt{UFL},\texttt{UFR},\texttt{URB},\texttt{FRD} \}$。如果我们把 $\texttt{FR'F'R}$ 看成一个基本操作，这个操作的支集和 $D$ 这个基本操作的支集的交集只有一个元素 $\texttt{FRD}$。 于是我们做交换子 $[[\texttt{F},\texttt{R'}],\texttt{D}]=\texttt{FR'F'RDR'FRF'D'}$，我们就可以获得一个三个角块 $\texttt{FUR},\texttt{FDR}$ 和 $\texttt{FLD}$ 的置换。 ## 生成元 前置知识：[群论](https://oi-wiki.org/math/algebra/group-theory/) 给出一些子群的性质： 1. 两个子群的交集也是一个子群。 2. 将一个群的元素个数称为群的阶数。对于群 $G$ 的某个子群 $H$，满足 $H$ 的阶数必定能整除 $G$ 的阶数。 :::info[性质 2 的证明] 不妨设 $G$ 的阶数为 $n$，$H$ 的阶数为 $m(m<n)$。 对于 $H=\{ H_1, H_2\dots H_m \}$，取元素 $g \in G $ 且 $g \notin H$，将 $g$ 作用在 $H$ 的每一个元素上： $H_g=\{ H_1g, H_2g\dots H_m g \}

得到结论：

  3. Hg \cap H = \empty(h_ag =h_b \Rightarrow g = h^{-1}_a h_b \in H)

然后我们可以拿另外一个不在 H 以及 H_g 中的元素，再进行同样的操作，得到 H_{g'}，可以证明跟之前的没有交集。

如此操作，直到取不出新元素为止。我们得到了 k 个大小与 H 相同的集合，且大小之和为 G。因此 km=n 得证。

:::

魔方实质上是一个由六个操作 \texttt{<U,D,L,R,F,B>} 生成的群。我们可以说，这六个操作是这个群的生成元。

可以举一些其他的例子：比如对于群 \{1, -1, i, -i\}，其二元运算为乘法，则 i 是一个生成元（因为每个元素都可以通过 i 生成），同理 -i 也是生成元。

一个群可以有多个生成元（即生成集合）。严谨地说，有生成子集 S 使得所有群 G 的所有元素都可以表达为 S 的元素和它们的逆元中的有限多个元素的乘积。将集合 S 生成的群记为 \texttt{<S>}。如果 S 是有限的，则群 G = \texttt{<S>} 为有限生成群（不一定是有限群）。

群 G 的生成集合的元素个数的最小值称为群 G 的秩。如果群的秩为 1，称其为循环群。

例如在魔方的生成群中，考虑 G=\texttt{<U>}，即对于魔方只能做 \texttt{U} 操作。显然，这个子集大小为 4。

至于怎么判定一个循环群的大小，我们可以发现这个东西就是上文讲过的置换，可以直接计算。如 G=\texttt{<FR>} 大小为 105。

我们可以对于给定的 x，研究大小为 x 的子群的存在性。

首先，我们知道魔方的总状态数为 S=43252003274489856000 = 2^{27} \times 3^{14} \times 5^3 \times 7^2 \times 11。根据前文的结论，群的子群大小满足倍数关系，即子群大小为 S 的倍数。

然后有 Sylow 第一定理：群 G 阶数为 k\times p ^m（p 与 k 互质）的有限群，则定有大小为 p_i(1 \le i \le m) 的子群。

例如存在大小为 2 的子群，大小为 9 的子群。我们只需要找到一个相应的 x 阶置换即可。

彩蛋：魔方中最大的循环群大小为 1260=2^2 \times 3^2 \times 5 \times 7。如操作 \texttt{R} ~~ \texttt{U2} ~~ \texttt{D'}~~\texttt{B}~~ \texttt{D'} 就需要按顺序重复这么多次才能复原。

对于生成元大于 1 个的群，情况会比较有意思一点。考虑 G=\texttt{<UU,RR>} 是长什么样的。

方便起见，将 \texttt{UU} 操作记为 \alpha，\texttt{RR} 操作记为 \beta。容易发现 \alpha = \alpha^{-1}（因为两次操作会复原）。

试计算 G 的大小？一个问题是里面有很多重复元素，比如 \alpha (\beta \alpha ) ^2 = (\beta \alpha) ^ 2 \beta 。

:::info[一些式子的推]

\begin{aligned} (\alpha \beta )^6 &= \alpha (\beta \alpha)^5 \beta=1 \\ &\Rightarrow \alpha (\beta \alpha)^5= \beta^{-1}=\beta \\ &\Rightarrow (\beta \alpha)^5 = (\beta \alpha)^4\beta \alpha = \alpha \beta \\ &\Rightarrow (\beta \alpha)^4 = (\alpha \beta)^2 &\Rightarrow \beta \alpha = (\alpha \beta)^5 \end{aligned} \alpha (\beta \alpha ) ^2 \cdot (\beta \alpha) ^ 2 \beta = (\alpha \beta)^6=1 (\beta \alpha) ^ 2 \beta \cdot (\beta \alpha) ^ 2 \beta = (\beta \alpha) ^ 2 \cdot (\alpha \beta) ^ 2=1

通过类似的方法也可以证明其他一些元素的相等。

:::

最终得到的元素集合大小为 12：

1 ~~ \alpha ~~ (\alpha \beta) ~~ (\alpha \beta)\alpha ~~ (\alpha \beta)^2 ~~ (\alpha \beta) ^2\alpha ~~ \beta ~~ (\beta\alpha) ~~ (\beta\alpha)\beta ~~ (\beta\alpha)^2 ~~ (\beta\alpha)^2 \beta (\beta\alpha)^3

将元素用 Cayley 图画出来是这样的：（单箭头代表操作 \alpha，双箭头为 \beta）

对于魔方的其他一些生成元组合，大小如下（图源@法会因由）：

从生成元的角度看，魔方群在这个意义上并不是置换群，而是一些操作的集合，但是这两个群本质或者群的结构是一样的，即他们同构。

降群法

降群法解最少步的基本方法就是，将魔方从一个初始群降解到更小的子群，最后到单位子群即还原状态。

上图是 1981 年 7 月 Thistlethwaite 提出的四阶段算法。在最坏情况下，采用这个方法需要 52 步转动。

在每一步 G_i \to G_{i+1} 中，我们通过一些操作将魔方的状态不断归约进更小的子群里。每一步减少的状态数我们称为减少因子。

1992年，Kociemba's algorithm 进一步改良了这个算法，采用直接降群至 G_3 然后还原的方法。在现代计算机上能够在几毫秒内得到一个不超过 20 步的还原步骤。

限于篇幅，本文不介绍具体的降群方法，进一步的学习可以参见魔方吧。

这里有一些优秀的程序降群实现。