魔方循环问题

winxos

问题表述如下：
对于魔方来说，给定一个指定步骤，请问重复旋转多少次会回到初始状态？
由于魔方状态有限，所以一定是会回到初始状态的。
具体举例：
如果进行R变换，需要4次，就是说将右侧面旋转4次就会回到初态；
如果进行R2变换，需要2次就可以了；
如果进行RU变换，则需要105次才会第一次回到初态！
附注：
对于不了解魔方公式定义的朋友我进行一下变换代号说明：
R：右手面顺时针旋转(right)
U：上面顺时针旋转(up)
F：前面顺时针旋转(front)
B：后面顺时针旋转(back)
L：左手面顺时针旋转(left)
D：下面顺时针旋转(down)
顺时针的定义为正面朝向该面进行判断，
后面加个2表示旋转两次，加' （一撇)表示逆时针旋转。

winxos

我做了一些简单的分析，比如对于长度为6的只有顺时针旋转的公式，循环次数最长为720，
回复后可以查看。

游客，如果您要查看本帖隐藏内容请回复

zed

群论问题. 对于任何一个步骤,魔方所有状态树目为这个次数的倍数

〇〇

很实际的问题

Lwins_G

为什么一定要回复才能查看呢。: (

wayne

Lwins_G 发表于 2013-12-31 03:51
为什么一定要回复才能查看呢。: (

回复查看之后，发现链接都已经失效，人世间悲催之事莫过如此，

如果你感兴趣，我可以帮你 把楼主 拉回来。

mathematica

同一个操作循环1260次,一定会回到原来的状态

Ickiverar

我以前编程算过这个，就是你给一套公式，我程序算做多少次能回去。
不过没试过随机生成公式的，我觉得楼上1260次这个结论很神奇，我要再做做。

mathe

魔方8个角上块可以相互交换，12个边上块可以互相交换，两者分别构成一个8阶置换群和12阶置换群。（这时还没有考虑这20个块的方向）
另外我们知道每次变换都是偶置换（可以通过偶数次两个元素交换得到），所以变换能够达到的情况也必须是偶置换，所以只有两种情况
i)8阶置换群中的偶置换搭配12阶置换群的偶置换
ii)8阶置换群中的奇置换搭配12阶置换群的奇置换
而置换群中每个置换都可以分解成一些不相交的轮换，比如(1345)(276)(8)就是8阶置换群中一个变换分解为互不相交的轮换的例子，就是1号到3号，3号到4号，4号到5号，5号到1号，2号到7号，7号到6号，6号到2号，8号保持位置不变。这样分解的好处是可以非常容易计算出这个置换的阶，它就是所有轮换数目的最小公倍数，比如这个例子就是[4,3,1]=12.另外需要注意的是偶数个数的轮换是奇置换，奇数个数的轮换是偶置换。
很显然每个置换的阶之和它这种分解模式相关，于是我们就可以很简单的穷举了。
比如8阶的可以分解为
8   (奇置换，阶数为8）
7+1 （偶置换，阶数7）
6+2 （偶置换，阶数6）
6+1+1（奇置换，阶数6)
5+2+1 (奇置换，阶数10）
...
我们只需要找出其中阶数大的如
5+3(偶置换，阶数15）
4+3+1（奇置换，阶数12）
而对于12阶置换群有
9+2+1 (奇置换，阶数18）
8+3+1(奇置换，阶数24）
7+5（偶置换，阶数35）
7+3+2(奇置换，阶数42）
6+5+1(奇置换，阶数30）
5+3+2+1(奇置换，阶数30）
...当然最好计算机穷举
然后分析它们的组合，要求奇置换配奇置换，偶置换配偶置换，组合阶数的最小公倍数尽量大
计算机得出最大组合是210，
比如S8中取6阶偶置换，S12中35阶偶置换，或
   S8中取7阶偶置换，S12中取30阶偶置换，或
   S8中取15阶偶置换，S12中取14阶偶置换，或
   S8中取10阶奇置换，S12中取42阶奇置换。
所以我们得出最多210轮后，所有的积木块都返回了它应该到达的位置。只是这时又部分积木块的取向可能不对，由于角上3种方向，边上2种，所以最多重复6次后可以使得取向也正确，所以最大阶数是210*6=1260

mathe

1. #include <stdio.h>
   
2. #include <set>
   
3. using namespace std;
   
4. int gcd(int a, int b)
   
5. {
   
6.     if(a==0)return b;
   
7.     return gcd(b%a, a);
   
8. }
   
9. int lcm(int a, int b)
   
10. {
    
11.     return (a/gcd(a,b))*b;
    
12. }
    
13. #define MAX_ORDER 12
    
14. set<int> even[MAX_ORDER+1];
    
15. set<int> odd[MAX_ORDER+1];
    
16. void calset()
    
17. {
    
18.     int i,j;
    
19.     set<int>::iterator it;
    
20.     even[1].insert(1);//order 1 reached for even perm (1)
    
21.     even[2].insert(1);//order 1 reached for even perm (1)(2)
    
22.     odd[2].insert(2);//order 2 reach for odd (12)
    
23.     for(i=3;i<=MAX_ORDER;i++){
    
24.        if(i&1){
    
25.           even[i].insert(i);
    
26.        }else{
    
27.           odd[i].insert(i);
    
28.        }
    
29.        for(j=i-1;j>=2;j--){
    
30.           //use number j
    
31.           if(j&1){
    
32.               //use even perm with j numbers
    
33.               for(it=even[i-j].begin();it!=even[i-j].end();++it){
    
34.                    even[i].insert(lcm(*it,j));
    
35.               }
    
36.               for(it=odd[i-j].begin();it!=odd[i-j].end();++it){
    
37.                    odd[i].insert(lcm(*it,j));
    
38.               }
    
39.           }else{
    
40.               //use odd perm with j numbers
    
41.               for(it=even[i-j].begin();it!=even[i-j].end();++it){
    
42.                    odd[i].insert(lcm(*it,j));
    
43.               }
    
44.               for(it=odd[i-j].begin();it!=odd[i-j].end();++it){
    
45.                    even[i].insert(lcm(*it,j));
    
46.               }
    
47.           }
    
48.        }
    
49.     }
    
50. }
    
51. 
    
52. void find_max_8_12()
    
53. {
    
54.     set<int>::iterator it1,it2;
    
55.     int maxorder=0;
    
56.     calset();
    
57.     for(it1=even[8].begin();it1!=even[8].end();++it1){
    
58.        for(it2=even[12].begin();it2!=even[12].end();++it2){
    
59.          int r=lcm(*it1,*it2);
    
60.          if(r>=maxorder){
    
61.              maxorder=r;
    
62.              printf("find order %d, even8=%d, even12=%d\n",maxorder, *it1, *it2);
    
63.          }
    
64.        }
    
65.     }
    
66.     for(it1=odd[8].begin();it1!=odd[8].end();++it1){
    
67.        for(it2=odd[12].begin();it2!=odd[12].end();++it2){
    
68.          int r=lcm(*it1,*it2);
    
69.          if(r>=maxorder){
    
70.             maxorder=r;
    
71.             printf("find order %d, odd8=%d, odd12=%d\n", maxorder, *it1, *it2);
    
72.          }
    
73.        }
    
74.     }
    
75.     printf("max order is %d\n",maxorder);
    
76. }
    
77. 
    
78. int main()
    
79. {
    
80.     find_max_8_12();
    
81.     return 0;
    
82. }
    

复制代码