数学研发论坛

 找回密码
 欢迎注册
查看: 244|回复: 9

[求助] 请问谁会用mathematica利用群论的知识与函数找出魔方公式?

[复制链接]
发表于 2018-11-10 16:23:35 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
能够提供的参考资料
  1. rot1 = Cycles[{{1, 3, 8, 6}, {2, 5, 7, 4}, {9, 48, 15, 12}, {10, 47,
  2.      16, 13}, {11, 46, 17, 14}}];
  3. rot2 = Cycles[{{6, 15, 35, 26}, {7, 22, 34, 19}, {8, 30, 33, 11}, {12,
  4.       14, 29, 27}, {13, 21, 28, 20}}];
  5. rot3 = Cycles[{{1, 12, 33, 41}, {4, 20, 36, 44}, {6, 27, 38, 46}, {9,
  6.      11, 26, 24}, {10, 19, 25, 18}}];
  7. rot4 = Cycles[{{1, 24, 40, 17}, {2, 18, 39, 23}, {3, 9, 38, 32}, {41,
  8.      43, 48, 46}, {42, 45, 47, 44}}];
  9. rot5 = Cycles[{{3, 43, 35, 14}, {5, 45, 37, 21}, {8, 48, 40, 29}, {15,
  10.       17, 32, 30}, {16, 23, 31, 22}}];
  11. rot6 = Cycles[{{24, 27, 30, 43}, {25, 28, 31, 42}, {26, 29, 32,
  12.      41}, {33, 35, 40, 38}, {34, 37, 39, 36}}];
  13. RubikGroup = PermutationGroup[{rot1, rot2, rot3, rot4, rot5, rot6}];
复制代码


参见mathematica软件的ref/PermutationGroup
比如交换2与47,5与16,
如何表达成rot1 rot2 rot3 rot4 rot5 rot6的形式呢?
QQ截图20181110161944.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-11-10 16:35:44 | 显示全部楼层
比如交换同时交换一个面上的三个棱块,用软件知道是可能的,但是不知道如何操作.
GroupElementQ[RubikGroup, Cycles[{{2, 5, 7}, {47, 16, 13}}]]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-11-10 17:11:51 | 显示全部楼层
(*检测1,5两个面之间的置换群是否能换掉三个棱(也就是上面与右面两个面来回转能否置换掉三个棱),
测试的结果是可以.但是却不知道如何操作,难道只能用穷举法与PermutationProduct这个函数,但是太麻烦了*)
GroupElementQ[PermutationGroup[{rot1,rot5}], Cycles[{{2, 5, 7}, {47, 16, 13}}]]
(*利用上面与右面不行,那只能用上面右面前面三个面*)
GroupElementQ[PermutationGroup[{rot1,rot5}], Cycles[{{6,8,3},{12,15,48},{11,14,17}}]]
GroupElementQ[PermutationGroup[{rot1,rot2,rot5}], Cycles[{{6,8,3},{12,15,48},{11,14,17}}]]

点评

数值解万岁!  发表于 2018-11-13 15:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-23 19:07:08 | 显示全部楼层
本帖最后由 .·.·. 于 2018-11-23 19:35 编辑
mathematica 发表于 2018-11-10 17:11
(*检测1,5两个面之间的置换群是否能换掉三个棱(也就是上面与右面两个面来回转能否置换掉三个棱),
测试的结 ...

学会了
感谢你提供了这样许许多多的关于群论的函数
其实你只离目的地差一个GroupElementToWord
  1. In[1]:=
  2. rot1 =   Cycles[{{1, 3, 8, 6}, {2, 5, 7, 4}, {9, 48, 15, 12}, {10, 47, 16, 13}, {11, 46, 17, 14}}];
  3. rot2 = Cycles[{{6, 15, 35, 26}, {7, 22, 34, 19}, {8, 30, 33, 11}, {12, 14, 29, 27}, {13, 21, 28, 20}}];
  4. rot3 = Cycles[{{1, 12, 33, 41}, {4, 20, 36, 44}, {6, 27, 38, 46}, {9, 11, 26, 24}, {10, 19, 25, 18}}];
  5. rot4 = Cycles[{{1, 24, 40, 17}, {2, 18, 39, 23}, {3, 9, 38, 32}, {41, 43, 48, 46}, {42, 45, 47, 44}}];
  6. rot5 = Cycles[{{3, 43, 35, 14}, {5, 45, 37, 21}, {8, 48, 40, 29}, {15, 17, 32, 30}, {16, 23, 31, 22}}];
  7. rot6 = Cycles[{{24, 27, 30, 43}, {25, 28, 31, 42}, {26, 29, 32, 41}, {33, 35, 40, 38}, {34, 37, 39, 36}}];
  8. RubikGroup = PermutationGroup[{rot1, rot2, rot3, rot4, rot5, rot6}];
  9. rtm1 = PermutationProduct[rot1, rot1, rot1];
  10. rtm5 = PermutationProduct[rot5, rot5, rot5];(*不会求逆只好这样将就了*)
  11. GroupElementToWord[PermutationGroup[{rot1, rot5}], Cycles[{{2, 5, 7}, {47, 16, 13}}]] /. {1 -> "rot1", 2 -> "rot5", -1 -> "rtm1", -2 -> "rtm5"}
  12. PermutationProduct @@ (GroupElementToWord[PermutationGroup[{rot1, rot5}], Cycles[{{2, 5, 7}, {47, 16, 13}}]] /. {1 -> rot1, 2 -> rot5, -1 -> rtm1, -2 -> rtm5})

  13. Out[8]= {"rot5", "rtm1", "rtm5", "rtm1", "rtm5", "rot1", "rot5", \
  14. "rot1", "rot5", "rot1", "rtm5", "rtm5", "rtm1", "rtm5", "rtm1", \
  15. "rtm5", "rot1", "rot5", "rot1", "rot5", "rot5", "rot1", "rtm5", \
  16. "rtm5", "rtm1", "rtm5", "rot1", "rot5", "rot5", "rtm1", "rtm5", \
  17. "rot1", "rtm5", "rtm1", "rtm5", "rot1", "rot5", "rtm1", "rot5", \
  18. "rot1", "rot5", "rot5", "rtm1", "rtm1", "rtm5", "rtm1", "rtm5", \
  19. "rtm1", "rot5", "rot5", "rot1", "rot5", "rot1", "rot5", "rtm1", \
  20. "rtm5", "rot1", "rtm5", "rtm5", "rtm1", "rtm5", "rot1", "rtm5", \
  21. "rtm5", "rtm1", "rtm5", "rot1", "rot5", "rtm1", "rot5", "rot1", "rot5"}

  22. Out[9]= Cycles[{{2, 5, 7}, {13, 47, 16}}]
复制代码
应当注意到,Mathematica只给出了一种“解法”(GroupElementToWord 使用 Minkwitz 算法)
并不能保证算出来的结果是最优的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-11-24 09:37:15 | 显示全部楼层
.·.·. 发表于 2018-11-23 19:07
学会了
感谢你提供了这样许许多多的关于群论的函数
其实你只离目的地差一个GroupElementToWord应当注意 ...

差不多得到了我想要的答案,不过这个生成的序列实在是太长了,我原本指望发明魔方公式呢,结果这下熄火了,不过知道如何产生的总比不知道强
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-11-24 09:52:28 | 显示全部楼层
.·.·. 发表于 2018-11-23 19:07
学会了
感谢你提供了这样许许多多的关于群论的函数
其实你只离目的地差一个GroupElementToWord应当注意 ...

这个问题解决了又来了一个新问题:如何把长度缩短?
产生的长度是网上给出的魔方的公式长度的好几倍,这个不具有可行性,
只具有理论价值
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-11-24 09:55:06 | 显示全部楼层
http://www.cube20.org/src/
也许这儿有需要的代码,但是我真的看不懂
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-24 14:41:21 | 显示全部楼层
本帖最后由 .·.·. 于 2018-11-24 15:08 编辑
mathematica 发表于 2018-11-24 09:55
http://www.cube20.org/src/
也许这儿有需要的代码,但是我真的看不懂


那个程序好像说的是暴力枚举之类的技巧
来自: Sophie Z(念念不忘,必有回响) 2010-08-10 09:57:05

今天早晨的消息: Morley Davidson 、 John Dethridge 、 Herbert Kociemba 和 Tomas Rokicki 宣称,他们已经利用计算机,完美地解决了魔方问题。他们验证了,任何一种魔方的初始状态都可以在 20 步以内解出。他们将 43,252,003,274,489,856,000 种初始状态分为了 2,217,093,120 组,再利用对称性和集合覆盖将规模缩小到了 55,882,296 组。他们的程序可以在 20 秒左右求解出一组问题的解法,最终利用 Google 提供的强大的计算机,彻底解决了魔方问题。
利用组合数学,我们能够证明,存在一种魔方初始状态,它需要至少 18 步才能解决。 1995 年, Michael Reid 找到了一种最少需要 20 步才能获解的魔方初始状态,因而将魔方问题的下界提高到了 20 。此后,数学家们猜想,任意给定一个魔方的初始状态,最多 20 步就能解决。 2008 年, Tomas Rokicki 和 John Welborn 证明了,任意一个魔方初始状态都可以在 22 步以内解决。 2010 年 7 月,这个上界终于降低到了 20 ,从而完成了对魔方最优解问题数十年来的探索。
详细的研究成果见这里:

http://www.cube20.org/
他们的程序可以在 20 秒左右求解出一组问题的解法
感觉如果换人来算这个……只能说一句“死得好惨”了……

程序的说明,看上去程序用了不少暴力枚举的技巧

In general, just type

   make

That should generate the programs hcoset.  This program requires
about 3.4GB to run.

The first time you run one of these programs, they will take a
while and generate a large pruning table.  On a fast machine
this will take about ten minutes.  The pruning table this program
needs is about 680MB in size.

General usage is:

   ./hcoset [options] [seq]

Either you can give a sequence, or you can use the -r switch
below, or you can do neither in which case it defaults to
running all 56 million cosets in the embedded cover.
A valid seq is some sequence of moves (in notation such as
R3F1U2R3U3B3F1L1F3U2---note, face in capital letters, followed
by required numeric twist of 1, 2, or 3 for each move), or it
can be a pair of numbers indicating a range of cosets to run.
This latter uses built-in information about what cosets to run
to prove 21, and then to add to that collection to prove 20.

In general, the first move should always be one of F1, F3,
R1, R3, B1, B3, L1, L3 as the other moves leave the position
in the Kociemba group and thus have no effect.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2018-12-3 13:28:12 | 显示全部楼层
.·.·. 发表于 2018-11-24 14:41
那个程序好像说的是暴力枚举之类的技巧

感觉如果换人来算这个……只能说一句“死得好惨”了……

别人用交换子或者共轭找魔方公式的,我看不懂
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-12-11 04:19 , Processed in 0.056567 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表