Thistlethwaite's algorithm 编程笔记
本帖最后由 aubell 于 2015-7-8 20:17 编辑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
但是注意，用的不是二进制，也不是十进制。
而是使用“阶乘进制”。
int permtonum(char* p){
int n=0;
for ( int a=0; a<4; a++) {
n*=4-a; //同二进制pack对比，类似二进制 shift left
//但是每一次都shift不同的量
for( int b=a; ++b<4; )
if (p<p) n++; //数大于号的个数
} //实际上是p>p
return n;
}
4. 四个元素的全排列划分为6个种类
四个元素的全排列可以划分为6个种类，怎样划分呢？
every one ^ first item
每一个元素与首元素异或，包括首元素。这样，首元素都是0了。
然后用"数大于号个数"的方法 pack-perm，就会成为三个元素的排列了。
用这种方法pack,非常巧妙。相同的种类类里，有着特殊的位置关系。
5. 两个轨道的相对扭转关系
两个轨道是如何pack到一起的呢？
看代码： case 5://tetrad choice, twist and parity
int corn,j,k,l,corn2;
// 8 bits, set bit if corner belongs in second tetrad.
// also separate pieces for twist/parity determination
k=j=0;
for(;++i<8;) //按照上面提到的固定的顺序查看所有位置
if((l=pos-12)&4){ //&4是就是 >=4 的意思了，因为小于4的元素&4都为0
//这一句是说，“如果是阴轨角”
corn=k++; //记录它出现的次序
n+=1<<i; //记录选择
}else corn=l; //如果是阳轨角，按顺序记录下它
//Find permutation of second tetrad after solving first
for(i=0;i<4;i++) corn2=corn]; //按照阳轨角出现的次序，
//查找阳角之家对应的大斜角出现的次序，并记录
//Solve one piece of second tetrad
for(;--i;) corn2^=corn2; // every one ^ first item
// encode parity/tetrad twist // 24种变成了6种
n=n*6+corn2*2-2; //pack起来,*6是把选择 shift left,
//为这六种情况空出存储位置
if(corn2<corn2)n++; //最终结果是选择和扭转pack在一起6.不用再理会parity了吗？
是。parity本质上是分两类讨论，这种pack方式分了六类。
包含了parity的情况还有角块围绕大斜线的扭转情况。所以不必再对parity讨论了。
7.进入G3的充分条件是什么？
在阴阳分轨以后，用上面的方式pack，得到的结果同还原态pack的结果一致。
喜欢这个，收藏了 正在学这个，收藏学习！
页:
[1]