关于魔方状态置换的快速解法

在前一篇日志中, 我把魔方从初始状态变换到给定状态的置换称为状态置换, 而当时想用强生成元来快速的找到该置换的表示, 由于我的知识有限, 未能成功. 今天我将用另一种方法实现快速找到这个状态置换. 换言之, 你只需要按照编号顺序写出给定状态下的颜色编号, 那么就可以利用程序机械的找出该置换.

首先还是让我讲讲基本原理. 一个基本的观察是, 每个小正方体(它由三个不同颜色组成三个可以看到的面)的颜色集合在转动过程中不会改变. 例如, 上篇日志中面对自己的编号为1,5,9的小正方体的颜色集合是{R,G,B}, 那么无论你怎么转动, 这个小正方体的位置可能会改变, 但是其各个上的颜色所成的集合是不会改变的. 于是我们可以通过首先对8个(2阶魔方的情形哈)小正方体的颜色集合三元组进行分类(有8个互不相交的颜色三元组组成), 而后, 在我们要寻找转动前后面的对应关系时, 可以先找到小正方体的对应关系, 一旦找到该对应关系, 通过颜色的对应可以得到编号的对应.

说起来可能很复杂, 但是我相信你自己把我上篇日志的那个例子中的状态置换找过一次就明白其要领了. 或者, 你也可以接着看我下面的代码和分析.

首先, 我们需要得到颜色按照编号排列的序列, 分别用iniorder, endorder来表示初始状态的颜色序列, 和给定状态的颜色序列. 明显, 按照前一篇日志的规定, iniorder={R, R, R, R, G, G, G, G, B, B, B, B, b, b, b, b, g, g, g, g, r, r, r, r}; 作为例子, 如前篇日志所假设的那个例子, 给定状态的颜色序列是:{R, R, R, R, G, G, b, G, B, B, r, B, b, g, r, b, g, g, g, b, r, G, B, r}; 这在Mathematica中可以如下表示:

接下来, 我们需要把这两个序列按照每个小方块来分组, 即位于同一个小方块的颜色分为同一个组. 同时, 由于我们最终是要通过颜色来寻找面的对应, 于是我们应该把每个颜色都联系着它的编号:

第一行是每个小正方体的编号分组, 而第二行是初始状态下颜色按照编号分组而构成的集合, 最后一行当然就是给定的状态下颜色按照编号分组而构成的集合. 为了便于理解, 我给出最后两行代码的输出结果(即颜色的分组结果):

他们分别由两行组成第一行是每个小正方体的编号分组, 第二行是与编号对应的颜色分组.

接下来, 为了根据颜色的分组, 找到对应编号的分组, 我们需要对每个组的颜色进行排序, 这样才能够通过程序判断两个颜色分组是相同的. 同样我给出mathematica代码:

例如, 给定状态下的颜色按照每个组的颜色升序排列后的分组为:

你可以看到原来给定状态下的 第一组是{{1,5,9},{R,G,B}}, 而按照颜色排序后变成{{9,5,1},{B,G,R}}. 需要提醒的是颜色和编号的对应关系一定要保持, 即排序前后1< ->R, 5< ->G, 9< ->B的关系没变. 否则后面就不能通过颜色寻找编号了.

这样, 一旦我们有了这个有序的颜色组, 那么就可以对比初始状态和给定状态的颜色组而得到面的对应:

这里, 我对代码作一些解释, 首先看到Position的作用是将第二个参数( sortedinigroup[[#, 2]] )在第一个参数(sortedendgroup[[All, 2]])中的位置找到, 而后我们还通过sortedendgroup[[*,1]]得到了该颜色在给定状态下的编号, 最后将这个操作对{1,2,3,45,6,,7,8}=Range[Length[smallcubeorder]] 中的每一个数都操作一遍. 这样当然就得到了与初始状态编号对应的给定状态的编号.

最后, 只需要找出这个将初始编号, 变为给定状态的编号的置换:

得到输出:

总起来说, 你只需将下面代码中的endorder所代表的颜色序列改为你需要的颜色序列, 运算后就可以直接得到状态置换:

注记

若将

替换为

则最终经过GAP计算得到的表示不需要取逆, 否则需要.