用 GAP 验证魔方群是 2-gen 的

Cielo

这里“魔方群”是指普通三阶魔方的状态集合，“2-gen 的” 是指由两个生成元生成。
也就是说，有两个公式 a 和 b，只需要交替做 a 和 b 若干次，就可以转出魔方的任意一个状态。

Speedsolving 论坛上有讨论这个问题的帖子，里面给了不少这种 {a，b} 组合，我选了一组来验证了一下。

a = U D’ = ( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19)(41,46,48,43)(42,44,47,45)(14,38,30,22)(15,39,31,23)(16,40,32,24)
（前5个括号里是 U，后5个括号是 D’）
b = LFR = (9,33,48,24,22,46,35,27,32,30,41,40,1,3,38,43,16,14) (6,17,11)(8,25,19) (4,18,5,36,45,21,23,20,44,37)(10,7,26,29,31,28,42,13,15,12)
（第1个括号是一个角块6-轮换，且伴随着色向变化，第2、3个括号是两个原地翻转的角块，后2个括号是一个棱块10-轮换）

a、b 生成的群 <a，b> 肯定是魔方群 G 的子群，而用 GAP 算出 <a，b> 的阶数与 G 的阶数相等，
所以 G = <a，b>，也就是整个魔方群可以由 a、b 生成。

wangjiyuan

期待这个问题能彻底解决

noski

一来就看到GAP这么先进的工具，赞一个~~~！
另外，我觉得一个公式遍历魔方也是可能的，魔方状态关系是图不是树。。

yq_118

原帖由 pengw 于 2010-4-28 07:27 发表 YQ_118愿意把GAP的算法原理分析一遍否？如果理解了算法原理，与魔方相关的群论知识也就基本搞清楚了

那个算法我也不懂啊，，GAP里面很多功能还不会用。

yq_118

原帖由 pengw 于 2010-4-28 07:08 发表 回7楼：如果不重复遍历状态，一个公式是不可能遍历所有状态，可以按照距根的最短路径（90度/步）将所有状态组织进树，不重复访问结点是不可能遍历整颗树，还有没有更好的组织方式？我认为树就是最好的组织方式，处 ...

这里不能用树来描述把，按公式不断做下去得到的树是无限的，去掉重复的状态剩下的有限状态的话，状态之间的一些联系就失去了。
描述这个应该用图，状态数量是有限的，两个状态能一步转换就连一条边，这个图里面存在哈密尔顿环的可能性挺大的。

pengw

YQ_118愿意把GAP的算法原理分析一遍否？如果理解了算法原理，与魔方相关的群论知识也就基本搞清楚了

pengw

回7楼：
如果不重复遍历状态，一个公式是不可能遍历所有状态，可以按照距根的最短路径（90度/步）将所有状态组织进树，不重复访问结点是不可能遍历整颗树，还有没有更好的组织方式？我认为树就是最好的组织方式，处理起来也很容易。

[ 本帖最后由 pengw 于 2010-4-28 07:09 编辑 ]

yq_118

原帖由 pengw 于 2010-4-27 16:42 发表 顺便，可以讨论一下某大师单个公式遍历所有状态的梦想？

这个是图论中的哈密尔顿环问题，貌似现在还没有有效的算法解决这个问题。

yq_118

that the cube is a 2-generator group, generated by
the moves

x=UBLUL'U'B' and y=RRFLD'R'.

Here's the usual 6 generators in terms of x and y (not the
shortest possible solutions, I daresay, but rather ones I figured
out using a probably inefficient method):

U=y'x'yxy'y'y'y'y'x'yyyyyxy'y'y'y'y'x'yyyyyx'x'x'x'y'y'y'y'y'xyyyyyx'y'y'y'y'y'x\
yyyyyx'
y'xy'y'y'y'x'yyyyyxxxxy'y'y'y'y'xyyyyyyx'x'x'x'
y'y'x'x'x'x'yxxxxxxyyyxxxxxxy'y'y'x'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'\
xyyyyyyyy
yyyyyyyyyyyyyyx'
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyyyyyyy\
yyyyyyyyyy
yyyyyyyyyyx'
y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyyyyyyyyx'yyyyyyyyyyyyyyyyyyyyyyyyyyyyxy'y'y'\
y'
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'x'
yyyyyyyyyyyyyyyyyyyyyyyyyyyyxy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y\
'y'y'x

D=y'y'y'x'y'x'x'x'x'yxyyx'yx'y'xxxxyxy'xy'y'xxxxxxyxxxxxxyxxxxxxyxy'y'y'y'y'y'y'\
y'y
'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyyyyyyyyx
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyxy\
yyyyyyyyyyy
yyxy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'
xy'y'y'y'y'y'y'y'y'y'y'xyyyyyyyyyyyyyyyyyyyyyyxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy
yyyxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyx
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'

F=y'x'yx'y'y'y'y'x'yyyyyxxxxy'y'y'y'y'xyyyyxy'y'y'xxxxyyxy'y'x'yyyyxxxxy'y'y'y'x\
yyy
yyyxxxxxxy'xxxxxxy'y'y'xxxxxxyxyyyyyyyyyyyyyyyyyyyyy
xy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyy\
yyyyyyyyyyy
yyxy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'x
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyxyyyyyyy\
yyyyyyyyyyy
yyyyxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyxyyyyyyyyyyyx
yyyyyyyyyyyxy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'

B=x'x'x'x'y'y'y'y'y'x'yyyyyxy'y'y'x'yyyx'x'x'x'y'y'y'xyyyx'y'y'y'y'y'xyx'yyyyxy'\
y'x'yyxx
xxy'y'xyyx'y'y'y'y'xyyyyxxxxxxyyxxxxxxy'y'y'y'xxxxxxy'y'y'y'xxxxxx
yyyxxxxxxy'y'y'y'y'y'y'y'xy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'\
y'y'y'y'y'y'xyy
yyyyyyyyyxyyyyyyyyyyyyyyyyyyyyyyxyyyyyyyyyyyyyyx
yyyyyyyyyyyyyyyyyyyyyxyyyyyyyyyyyyyyxyyyyyyyyyyyyyyyyyyyyyyyyyyyy

R=yyyyyyyyyyyyyyyyyyyyyyx'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xy'y'y'y'y\
'y'y'y'y
'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'x'
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyxxxxy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y\
'y'y'
y'y'y'y'y'y'y'y'y'xyyyyyyyyyyyx'
yyyyyyyyyyyyyyyyyyyyyyxxxxy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyyy\
yyy
yyyyyyyyyyx'yyyyyyyyyyyyyyyyyyyyyyx
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xxxxxxyyyyyxxxxxxy'xxxxxxy'xxxxxxy'y\
'y'xyy
yyyyyyyyyyyyyyyyyyyxyyyyyyyyyyyyyyyyyyyyyx
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyyyyyyyyyyyyyyyyy\
yyyyyyy
xy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'x
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xyyyyyyyyyyy

L=yx'yyyx'y'y'y'xxxxyyyxy'y'y'xy'x'y'y'y'x'x'x'x'yyyxy'xxxxxxyyyyyyxxxxxxy'xxxxx\
x
y'y'y'xxxxxxy'xyyyyyyyxyyyyyyyyyyyyyyyyyyyyyx
yyyyyyyyyyyyyyyyyyyyyxyyyyyyyyyyyyyyyyyyyyyxyyyyyyyyyyyyyyxy'y'y'y'y'y'y'x
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'x
y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'xy'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y'y\
'y'y'y'y'xy'y'y'y'y'
y'y'y'y'y'y'x

也没那么夸张，可以先把基本的操作表示出来，然后任意一种状态都能用x，y来表示。顶多几百次。如果利用计算机搜索，应该可以找到步数更少的表示方法（另一种意义的最少步）。

pengw

顺便，可以讨论一下某大师单个公式遍历所有状态的梦想？