[原创]魔方循环变换理论概述（待完善）

ggglgq 发表于 2004-6-3 14:33:33

魔方循环变换理论概述（待完善）
一、魔方循环变换的定义：
 1.先给出几个记号：
 在本理论中，统一规定： 小写字母表示步长为 1 的变换； 大写字母表示由步长为 1 的变换构成的变换。
 对于变换 A ，若它的积为单位元，则记为： A = 1 ；
 对于变换 A ， length(A) 表示变换 A 的长度; half(A) 表示 length(A) 的一半并取整; 例如: A = a1 a2 a3 a4 a5 a6 ； length(A) = 6 ， half(A) = 3 。 又如: A = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11； length(A) = 11 ， half(A) = 5 。
 对于变换 A ， circle0(A) 表示变换 A 的首尾相连的旋转变换，旋转方向 继承变换 A 的方向； 注意：变换 circle0(A) 是没有首尾的，但却是有方向的。 如：circle0(a1 a2 a3) 与 circle0(a3 a2 a1) 是反方向。 any(A,n) 表示变换 A 的任意一个相连的长度为 n 的子变换；
 2.魔方循环变换的定义： 对于有效变换 A ，如果 A = 1 ，并且 any(circle0(A),half(A)) 都是最少步变换，则称变换 A 为循环变换。记作： 循环变换 A 或 circle(A)
二、魔方循环变换的例子： 这里以正六面体三阶魔方为例说明： 由魔方循环变换定义得：宇宙飞碟所举的 [长度为四的循环变换] 、 [长度为八的循环变换] 、[长度为十二的循环变换] 、[长度为十四 的循环变换] 、 [长度为十六的循环变换] 均为正确循环变换的例子。 但宇宙飞碟昨天举的 [长度为 210 的循环变换] 、 [长度为 126 的循环变换] 是错的，是他和大家开玩笑呢。
 对于一般的魔方，设它的 [最少步最长的变换] 的长度为 x ，那么 它的循环变换长度最长不过为 2*x+1 。对于正六面体三阶魔方，虽然我还 不清楚它的 [最少步最长的变换] 的长度为多少，但肯定不会超过 30 ， 它的循环变换长度必然小于 61 。因此对于正六面体三阶魔方，宇宙飞碟 昨天的 [长度为 210 的循环变换] 、[长度为 126 的循环变换] 是错的。 不过如果作为不严谨的理解，可以另外再定义一个广义循环变换， 不妨称上面的“魔方循环变换的定义”为狭义循环变换。这样宇宙飞碟 昨天举的 [长度为 210 的循环变换] 、 [长度为 126 的循环变换] 是 两个广义循环变换。
 明天再为大家证明 [循环变换] 的首尾无关性！例如：若变换 a1 a2 a3 为 循环变换，则变换 a1 a2 a3 与 a2 a3 a1 和 a3 a1 a2 为同一个循环变换。 
[此贴子已经被作者于2006-4-1 14:35:26编辑过]

宇宙飞碟 发表于 2004-6-3 14:59:02

下面我给出我所知道的真正意义上的几个循环变换：

长度最少的循环变换 [长度为 4 ] ：
<APPLET code=lrubik.class codeBase=http://www.mf8.com.cn/Java/3a/ height=145 width=125><PARAM NAME="pos" VALUE="fffffffffbbbbbbbbbaaaaaaaaacccccccccdddddddddeeeeeeeee"><PARAM NAME="move" VALUE="R1R1R1R1"></APPLET>
value="R1R1R1R1"

长度为八的循环变换：
<APPLET code=lrubik.class codeBase=http://www.mf8.com.cn/Java/3a/ height=145 width=125><PARAM NAME="pos" VALUE="fffffffffbbbbbbbbbaaaaaaaaacccccccccdddddddddeeeeeeeee"><PARAM NAME="move" VALUE="R1L1R1L1R1L1R1L1"></APPLET>
value="R1L1R1L1R1L1R1L1"

长度为十二的循环变换：
<APPLET code=lrubik.class codeBase=http://www.mf8.com.cn/Java/3a/ height=145 width=125><PARAM NAME="pos" VALUE="fffffffffbbbbbbbbbaaaaaaaaacccccccccdddddddddeeeeeeeee"><PARAM NAME="move" VALUE="B1U1B3R3U1R3F1R1F3U3R1U3"></APPLET>
value="B1U1B3R3U1R3F1R1F3U3R1U3"

长度为十四的循环变换：
<APPLET code=lrubik.class codeBase=http://www.mf8.com.cn/Java/3a/ height=145 width=125><PARAM NAME="pos" VALUE="fffffffffbbbbbbbbbaaaaaaaaacccccccccdddddddddeeeeeeeee"><PARAM NAME="move" VALUE="R1F1D1F3D3R3U1R1D1F1D3F3R3U3"></APPLET>
value="R1F1D1F3D3R3U1R1D1F1D3F3R3U3"

长度为十六的循环变换：
<APPLET code=lrubik.class codeBase=http://www.mf8.com.cn/Java/3a/ height=145 width=125><PARAM NAME="pos" VALUE="fffffffffbbbbbbbbbaaaaaaaaacccccccccdddddddddeeeeeeeee"><PARAM NAME="move" VALUE="F3L3F1R1F3L1F1L1U1L3U3R3U1L1U3L3"></APPLET>
value="F3L3F1R1F3L1F1L1U1L3U3R3U1L1U3L3"

宇宙飞碟 发表于 2004-6-3 15:06:39

两个广义循环变换：
<APPLET codeBase=http://www.mf8.com.cn/Java/3a/ code=lrubik.class width=125 height=145><PARAM NAME="pos" VALUE="dddddddddfffffffffeeeeeeeeebbbbbbbbbcccccccccaaaaaaaaa"><PARAM NAME="move" VALUE="U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1U1R1"></APPLET> 即：105 个 "U1R1"<APPLET codeBase=http://www.mf8.com.cn/Java/3a/ code=lrubik.class width=125 height=145><PARAM NAME="pos" VALUE="dddddddddfffffffffeeeeeeeeebbbbbbbbbcccccccccaaaaaaaaa"><PARAM NAME="move" VALUE="U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3U1R3"></APPLET>
即：63 个 "U1R3"

cube_master 发表于 2004-6-3 23:05:43

<DIV class=quote>以下是引用宇宙飞碟在6/3/2004 2:49:44 PM的发言：

呵呵，定理：如果恩师在 <a href="http://www.supersoko.com/bbs" target="_blank" >www.supersoko.com/bbs</A> 上是 [哥白尼]，那么在本论坛上是“发现了魔方广义循环变换、狭义循环变换”的 [爱因斯坦] 。
不知大家是否支持该定理呢？请大家跟贴发表意见！</DIV>
我正在努力的理解。

ggglgq 发表于 2004-6-4 08:46:09

本帖最后由 ggglgq 于 2013-10-2 18:52 编辑

　　
　　
三、同一变换的定义：
 同一变换的定义：若两个变换 A 、B 满足: AB=BA，则称 A 与 B 可交换，并且规定 AB 与 BA 是同一变换。
 由同一变换的定义得：若变换 A = a1 a2 a3 ... ax 为循环变换，那么
 a1 a2 a3 ... ax = 1
 所以
 a1 (a2 a3 ... ax) = (a2 a3 ... ax) a1 = 1
 因此 a1 (a2 a3 ... ax) 与 (a2 a3 ... ax) a1 是同一变换。
 故
 a1 a2 a3 ... ax 与 a2 a3 ... ax a1 是同一变换。
 又由变换 A = a1 a2 a3 ... ax 为循环变换，所以
 any(circle0(A),half(A)) 都是最少步变换，故
 a1 a2 a3 ... ax 与 a2 a3 ... ax a1 是同一循环变换。

 同理可得： a2 a3 ... ax a1 与 a3 ... ax a1 a2 是同一循环变换。
 .......................................
 .......................................
 .......................................
 这样我们就证明了 [循环变换] 的首尾无关性！即：
 A = a1 a2 a3 ... a(x-1) ax 为循环变换，那么所有
 a1 a2 a3 ... a(x-1) ax
 a2 a3 ... a(x-1) ax a1
 a3 ... a(x-1) ax a1 a2
 ................
 ax a1 a2 a3 ... a(x-1)
 都为同一循环变换。因此在前面的循环变换定义中，把它们统一记作：
 循环变换 A 或 circle(A)

四、创建《魔方循环变换理论》的意义，即循环变换理论的用途：
 1.帮我们找到魔方任意一个变换的最少步变换；
 2.帮我们找到魔方最少步最长的变换；
 3.魔方中心粒最少步变换的解决；
 4.利用计算机找出某种魔方所有循环变换的[集合]；
 5.利用 4. 的[集合]解决该魔方的上述 1. 2. 3. 的最少步变换问题。

五、利用计算机找出某种魔方所有循环变换的[集合]：
 想要“利用计算机找出某种魔方所有循环变换的[集合]”应该是这一
理论的最精彩的部分，因为随着 [循环变换 A] 的长度的增大，一个这样
的变换就代表 any(circle(A),n) [ n<=half(A) ] 的所有最少步变换，
它的利用效率是相当高的。

 愿对计算机编程感兴趣的魔方爱好者，能注意如何“利用计算机找出
某种魔方所有循环变换的[集合]”来为我们编程服务。同时欢迎大家一起
研究探讨、补充完善魔方循环变换这一理论，使之有更广泛的应用。

 因最近很忙，今后不能天天泡网，只能零星来几次，愿大家能谅解。
若有建议，可以直接回帖提出，或给我发 Email 联系： ggglgq@sina.com

cube_master 发表于 2004-6-4 16:10:13

能得到魔方的所有组合的循环变换至少需要多少步？

cube_master 发表于 2004-6-4 16:56:53

<DIV class=quote>以下是引用ggglgq在6/3/2004 2:33:33 PM的发言：

对于变换 A ，
 length(A) 表示变换 A 的长度;
 half(A) 表示 length(A) 的一半并取整;
 例如: A = a1 a2 a3 a4 a5 a6 ；
 length(A) = 6 ， half(A) = 3 。
 又如: A = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11；
 length(A) = 9 ， half(A) = 5 。</DIV>
请问
又如: A = a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11；
 length(A) = 9 ， half(A) = 5 。
是否应该是：length(A) = 11 ， half(A) = 6

ggglgq 发表于 2004-6-4 18:33:44

我想不能单纯用 “循环变换至少需要多少步？” 来回答，因为：
对于一般的魔方，设它的 [最少步最长的变换] 的长度为 x ，那么
它的每一个循环变换的长度都不会超过 2*x+1 。但我们不能由一个像这样的
长度为 2*x+1 的循环变换得到魔方的所有最少步变换。
例如：x = 3 是某一魔方的 [最少步最长的变换] 的长度。
 a1 a2 a3 b1 b2 b3 为它的一个循环变换，
那么它只能代替
 a1、a2、a3、b1、b2、b3
 a1 a2、a2 a3、a3 b1、b1 b2、b2 b3、b3 a1
 a1 a2 a3、a2 a3 b1、a3 b1 b2、b1 b2 b3、b2 b3 a1、b3 a1 a2
共十八个最少步变换。
[ 注意：长度为 4、5、6 的变换不是最少步变换。如 a1 a2 a3 b1
不是最少步变换，因为 a1 a2 a3 b1 = -b3 -b2 ，其中 -b3、-b2 分别
表示 b3、b2 的逆变换]
但它却不能代替这种魔方的所有最少步变换。

比如开发正六面体三阶魔方最少步软件 Cube 的作者 H.Kociemba
采用 The Two-Phase Algorithm 算法求解时，特别制作了一个大小是 1G
左右的“表”，便于求解时计算和查表。
对于正六面体三阶魔方，虽然我还不清楚它的 [最少步最长的变换]
的长度为多少，但肯定不会超过 30 ，它的循环变换长度必然小于 61 。
利用《魔方循环变换理论》制作所有循环变换的 [集合]，这个 [集合] 的
大小估计小于 H.Kociemba 制作的大小是 1G 左右的“表”。
[ 注：现在我还没有着手研究这一问题，准备在制作 {所有循环变换的
[集合]} 时，还要尽可能采用旋转、对称等技巧，使任何一个循环变换能
代替 {各种和它旋转、对称后都相同的循环变换}，这样制作出来的 {所有
循环变换的 [集合]} 才能更小，利用效率更高。]



[此贴子已经被作者于2005-5-8 18:12:07编辑过]

ayi2000 发表于 2004-6-5 22:11:28