三轮换的故事外传：作案工具

earthengine

有很多人搞不懂状态、变换和公式的联系和区别，所以这里澄清一下：

状态是节点在各个位置的摆放方式。它相当于数学上的一个点，没有开始也没有终结，它就是一个点。所有这些状态组成状态空间

变换是一套法则，或者用乌木的话说，是变化的模式。任意给定一个状态，变换能给我们另一个状态。这可以比作数学函数，自变量是状态，定义域是状态空间。

公式是变换的表现形式。表达变换的方式非常多，可以用公式，变换表（列出每个位置上的节点该如何移动的表），也可以用矩阵，等等。全等公式只是在表达同一变换这个意义上全等，其余方面如步长等是不等的。

在研究一些问题的时候，公式不是最方便的表达变换的形式。下面我介绍我最常用的一套表达方法

• []表示空循环，它不改变任何东西。
• [123]表示一个循环，它把位置1上的节点移动到位置2，位置2上的节点移动到位置3，位置3上的节点则回到1上。这个表达中不允许出现重复符号，否则就是非法的。
• [123][45]表示两个循环，把位置1上的节点移动到位置2，位置2上的节点移动到位置3，位置3上的节点则回到1上，同时位置4上的节点与位置5上的调换。
• [123][15]表示一个复合操作，把位置1上的节点移动到位置2，位置2上的节点移动到位置3，位置3上的节点则回到1上。执行完这些操作后，还要把位置1上的节点和位置5的节点调换。因此，它等价于[1235]。容易看出，把两个独立循环看成复合操作也没有错。

在写下一个循环式之后，如果有不被列出的节点，则它不在这个循环式所代表的变换相关位置上。这样我们完全可以从一个循环式得到它的变换表。
正如在最后一条规则所显示的，在以上规则下，一个变换仍然可以有多种表达。但是我们另有以下化简规则：

• 把任何空括号消除，除非消掉它就没有东西剩下了。
• 把任何重复出现的节点消去，方法见下。
• 在任何方括号内，把最小的数字移动到最前面。规则是：每次把最后一个符号移到最前面，保持相对顺序不变。
• 把所有括号对按照第一个符号的编号排序。

在这些化简规则下，任意变换只能有唯一的一个最简表达方式。这为我们判定变换的等同性提供了方便。

还需要阐述消节点的方法。我们一并描述如何给出变换表之后得出它的表示

假定我们有一个变换表1->2,2->4,3->3,4->1,5->6,6->5。我们首先把所有不变的编号去掉（这里是3）找出编号最小的节点1然后写下 [1 因为1要变成2，所以它的左边要写2。然后2要变成4，所以接着写4，余类推直到回到1。这时候我们不能写1因为已经出现过了。所以我们写右括号： [124] 现在已经完成一个循环。我们要重新扫描变换表直到找到一个还没有处理过的最小节点重复以上步骤。这里是5（3已经被去掉了）。结果为 [124][56] 现在已经没有尚未处理的节点，因此算法结束。该算法总是得到最简循环式。因为我们已经有了从变换表到循环式的双向算法，因此对于一个非最简的循环式，只要先将它变成变换表再得到最简式即可。熟练之后，你将能直接扫描未化简的循环式得到最简式。但是这时，为了方便你会想到不预先把不变的编号去掉，而是在开始一个括号的时候，首先确保当前处理的节点最终不会变回原位然后才开始书写循环，或者留下一些只有一个符号的括号，到最后删掉。

对循环式求逆可以用笨办法，先变变换表，求逆，再化简。但是有一个简单的方法：任何循环保持第一个元素不变，把其余元素的顺序颠倒，就能得到循环的逆。把所有循环求逆，就得到循环式的逆。

如果我们有了所有基本动作的循环式，那么我们可以把一个公式里面所有基本动作换成它的循环式表示，然后予以化简，就得到公式所代表变换的循环式。但是，不要问我怎么从循环式求公式！循环式只能告诉你这个变换能把复原态变成什么样子，如果你能把它化成公式，对公式求逆你就能复原这个魔方了！

现在我们来应用这个方法解决乌木提出的问题：LU魔方角块的自由度问题。

LU只不过是两个四轮换而已。但是它们有两个相连的交点。在交点处L和U的转动方向是相反的。所以我们可以据此进行编号L=[1234]，U=[3564]。

第一个节点的固定永远不是问题。因此我们只要关心如何将节点移动到2这个位置。我们能不能找到一个保持1不变的公式，能把3456中的某一个移动到2呢？让我们祭出法宝——相似变换来解决这个问题。因为我们想保持L不变，因此希望寻求U的相似变换。其中最简单的候选也许是(L)(U)(L')了。我们看看它的循环式：

[1234][3564][1432]

化简后得到[2563]。成功了！356等位置现在可以都到达位置2了，而1保持不动。还有一个4无法达到。根据相似变换原理，U能把4变走，所以我们再来看看

(U)(L)(U)(L')(U')=[3564][1234][3564][1432][3465]

这个循环式很长，不过化简后就是[2354]。这样2就可以到达位置4了。

循环式和其它表示方法本质上完全一样，但在使用上有几个优点：

• 循环式把变换的很多内部结构都揭示出来了。比如，从循环式求它的周期很容易。同样的任务用变换表就难一点。用公式的话，很难一眼看出。
• 循环式用一种简洁的方式把变换表示成一种具有唯一性的方式。这样我们判断全等公式就更容易了。

不过，对循环式有一种容易发生的误解是，如果循环式的结构相同（包含同样数目的循环，每个循环的长度也相同），那么误以为两个变换一定是相似的。这个不一定的。是否相似公式要看是否存在把一个变换为另一个的公式。尽管两个公式的结构相同，但是它不一定就能相似。比如，棱块有三轮换，角块也有，但这两种三轮换并不是相似的。当然，这是因为它们作用于不同的族。那么如果限于同一个族，能否说结构相同（且族外的变换全等）就一定相似呢？恩，这个问题我还没有答案。如果你知道，你来告诉我好吗？

知Shmily足

沙发，LZ辛苦啊，佩服

jjjj2022

LZ 好像有耐心 精神可佳

yzfa9860

吧里又多一位高人啦

乌木

“状态是节点在各个位置的摆放方式”，这一叙述隐含了节点的色向变化。
“变换表（列出每个位置上的节点该如何移动的表）”这一叙述似乎看不出节点的色向变化。
哈，我有点贪心不足。

earthengine

原帖由 乌木 于 2008-8-20 15:49 发表
“状态是节点在各个位置的摆放方式”，这一叙述隐含了节点的色向变化。
“变换表（列出每个位置上的节点该如何移动的表）”这一叙述似乎看不出节点的色向变化。
哈，我有点贪心不足。

色向变化我还没有很好的处理方式。但之前在理论区贴的24状态帖子里面，我有提到，对于魔方而言，角块可看成三个节点的连锁，棱块则是2个节点。如果中心块有向则是4个节点。这样就可以应用这个表述了。

乌木

理论区另一版主邱志红的《魔方色向定理》一帖（http://bbs.mf8-china.com/viewthr ... &extra=page%3D8），我是没本事看，你不妨看看，再向我们讲解讲解。

smok

这是可以证明，而且是已经完成的证明，一直想看看其它高手是如何搞定这个问题，会不会又是让三置换来证明三置换？还是将三置换的组合使用看成是一项重大个人成果？

[ 本帖最后由 smok 于 2008-8-20 19:39 编辑 ]

pengw

<P>三置换的故事真有这么精彩？我怎么横看竖看，都觉得三置换是最平凡的一个变换，在N阶定律定律中，只有一句话：位移簇任意三个块都可以独立进行三置换，难到说得还不够清楚？难到还要将三置换的使用作为一个故事来表达？这个故事要说多久？好像跟魔方状态数等长啊，哈哈哈</P>
<P>&nbsp;</P>
<P>即是要大讲特讲，也不过就是：</P>
<P>&nbsp;</P>
<P>奇：5元，7元，9元，11元，13元，17元，19元，21元，23元</P>
<P>偶：2元，6元，8元，10元，12元，14元，16元，18元，20元，22元，24元</P>
<P>&nbsp;</P>
<P>&nbsp;</P>
<P>再多讲一点，也不过就是加点相似变换</P>
<P>再多讲一点，就是扰动了，也不过就是偶配偶的同性恋故事，也没有什么啊</P>
<P>&nbsp;</P>
<P>这样都是N年前的老生长谈，难到还有什么事情说不明白硬要去套点什么拒人于千里之外的威猛术语，以显示自已不凡的的气度，这种事以前也发生过多少，到头来甚至不能自园其说，不好嘛</P>
<P>&nbsp;</P>

[ 本帖最后由 pengw 于 2008-8-20 20:09 编辑 ]

ggglgq

earthengine 先生的魔方理论才能令人敬佩，提出了许多全新的见解！

    1、建议 earthengine 先生能在一个主题帖中系统发表您的理论，以便大家
学习探讨！

    2、建议 earthengine 先生能完善您的理论体系，包括研究目的、方向、成果
>等的展示，基本定义、术语、概念等的描述，相关公理、定理、猜想等的体系等等。

    3、如果您愿意，本人可以固顶您的理论帖，以便广大魔友随时探讨研究！