Thistlethwaite's algorithm 编程笔记

aubell

1.第一步 G0->G1 不是重点，也不是难点。把所有的棱方向摆成一致。
2.第二步 G1->G2 如果要存储所有状态，内存的需要稍微大些，不过可以接受。
         是重点，但不是难点。
3.第三步 G2->G3 内存的需要很少，但这个步骤是整个算法中最难的地方。
        放到后面解释。
4.第四步 G3->I 内存的需要比较大。假如存储所有状态，难在把棱的状态同数字
         一一对应。很多的实现要么采用两倍大小的空间来存储，要么使用hash
         技术存储。个人编程的时候，采用了两倍大小的空间。对于角的排列，如果
         理解了第三步的办法，那么这一步角排列是很容易pack的。
5.棱和角可以任意组合pack。

进入G3的充分必要条件：
1. 先看Jaap的代码：
内部实现时，角的排列次序
UFR UBL DFL DBR   DLB DRF URB ULF
注意这个次序的特点
(1）前4个是一组，我合称其位置为阳轨道;后面四个是一组，我合称其为阴轨道。
(2) 同一个轨道里的角处在面对角线上，不相邻。我称这种位置关系为小尖。
(3) 注意两个轨道对应的排列次序，UFR同DLB三个字母都不同，也就是说，
    它们处于立方体的大对角线上，我称这种位置关系为大斜。
    UBL同DRF也是大斜的位置关系。后面依次都是。
2. 三个元素的全排列
   三个元素只有六种排列方式。
   编码很容易：
  012 编码为 0< (小于号表示第二个元素小于第三个元素）
  021 编码为 0> (第一个元素原样抄写）
  102 编码为 1<
  120 编码为 1>
  201 编码为 2<
  210 编码为 2>
然后把 “<” 编码为0, “>” 编码为1，再pack成二进制数字
如 1> ，首位乘以2加上大于号对应的1,编码为3
3. 很多元素的排列
   也是用类似的方法来pack和unpack
   但是注意，用的不是二进制，也不是十进制。
   而是使用“阶乘进制”。

1.    int permtonum(char* p){
   
2.         int n=0;
   
3.         for ( int a=0; a<4; a++) {
   
4.                 n*=4-a;  //同二进制pack对比，类似二进制 shift left
   
5.                          //但是每一次都shift不同的量
   
6.                 for( int b=a; ++b<4; )
   
7.                         if (p[b]<p[a]) n++; //数大于号的个数
   
8.         }                                              //实际上是p[a]>p[b]
   
9.         return n;
   
10.         }

复制代码

4. 四个元素的全排列划分为6个种类
   四个元素的全排列可以划分为6个种类，怎样划分呢？
   every one ^ first item
   每一个元素与首元素异或，包括首元素。这样，首元素都是0了。
   然后用"数大于号个数"的方法 pack-perm，就会成为三个元素的排列了。
   用这种方法pack,非常巧妙。相同的种类类里，有着特殊的位置关系。
5. 两个轨道的相对扭转关系
   两个轨道是如何pack到一起的呢？
   看代码：

1. case 5://tetrad choice, twist and parity
   
2.   int corn[8],j,k,l,corn2[4];
   
3. // 8 bits, set bit if corner belongs in second tetrad.
   
4. // also separate pieces for twist/parity determination
   
5. k=j=0;
   
6. for(;++i<8;) //按照上面提到的固定的顺序查看所有位置
   
7. if((l=pos[i+12]-12)&4){ //&4是就是 >=4 的意思了，因为小于4的元素&4都为0
   
8.                         //这一句是说，“如果是阴轨角”
   
9. corn[l]=k++;           //记录它出现的次序
   
10. n+=1<<i;               //记录选择
    
11. }else corn[j++]=l;     //如果是阳轨角，按顺序记录下它
    
12. //Find permutation of second tetrad after solving first
    
13. for(i=0;i<4;i++) corn2[i]=corn[4+corn[i]]; //[color=Magenta]按照阳轨角出现的次序，
    
14.                  //查找阳角之家对应的大斜角出现的次序[/color]，并记录
    
15. //Solve one piece of second tetrad
    
16. for(;--i;) corn2[i]^=corn2[0]; // every one ^ first item
    
17. // encode parity/tetrad twist   // 24种变成了6种
    
18. n=n*6+corn2[1]*2-2;             //pack起来,*6是把选择 shift left,
    
19.                                  //为这六种情况空出存储位置
    
20. if(corn2[3]<corn2[2])n++;       //最终结果是选择和扭转pack在一起

复制代码

6.不用再理会parity了吗？
  是。parity本质上是分两类讨论，这种pack方式分了六类。
包含了parity的情况还有角块围绕大斜线的扭转情况。所以不必再对parity讨论了。

7.进入G3的充分条件是什么？
  在阴阳分轨以后，用上面的方式pack，得到的结果同还原态pack的结果一致。

轻描淡写3333333

喜欢这个，收藏了

xyfox

正在学这个，收藏学习！