魔方吧·中文魔方俱乐部

标题: 三盲不同方式处理棱块奇偶编码长度对比 [打印本页]

作者: 唐龙3bf 时间: 2018-3-16 12:26:28 标题: 三盲不同方式处理棱块奇偶编码长度对比

本帖最后由唐龙3bf 于 2018-3-19 11:33 编辑

手机或平板排版字太大的魔友，请拉到最下方选择“电脑版“页面，即可解决。

一、引子

2017年年底，勺子发表了《三阶盲拧知识体系总纲》这一篇教程。
勺子在反编法的讨论中，给出了不同的情况，曾经想过要编写一个随机程序来分析出现不同情况的概率。我个人是一个沉迷于魔方的程序猿，便思考了一下这一问题。期间有过一些问题卡壳，大约过了一周后思路有所清晰，联系了勺子，并主动揽下了这一任务。
对于分析过程不感兴趣只想要结论的朋友可直接从第六章开始阅读。

作者: 唐龙3bf 时间: 2018-3-16 12:27:48

本帖最后由唐龙3bf 于 2018-3-16 17:52 编辑

二、问题的分析

首先最重要的问题就是有多少状态值得我们讨论。毕竟魔方的总状态数很多很多，大约4.32e19种不同的情况。如果只是单独讨论棱块对其的影响，则总共只有12!*2^11种不同的情况。由于我们只考虑编码的长度，所以棱块的方向对于总编码数并无影响，虽然原地翻棱会增加我们实际使用的公式量，但是我们并不会对其进行编码，不予讨论，此时总状态数减少为12!种不同的情况。那么在什么情况下我们需要进行反编呢，只有奇状态，总状态数再次减少，为12!/2=239500800。
说明：在本文中奇状态即我们平时所说的有奇偶状态。相对应的，偶状态就是没有奇偶的状态。

作者: 唐龙3bf 时间: 2018-3-16 12:30:26

本帖最后由唐龙3bf 于 2018-3-16 18:34 编辑

三、状态的存储

其次我们需要解决计算机内部存储魔方状态的问题。因为我们只考虑棱块，所以我们只需要按照顺序记录下来每一个位置实际的块的编码。

例子：F2 D' U2 L2 D2 B2 D2 U' B' R2 U B' R' F' D' F L' B R' F
看到A位置的块要到W，那么此时的状态序列为W；
看到C位置的块要到C，那么此时的状态序列为WC；
看到E位置的块要到F，那么此时的状态序列为WCE（不考虑方向）；
………………
看到Y位置的块要到T，那么此时的状态序列为WCEGOQAYMIKS。
按照这样的方式我们可以得到一个打乱对应的状态序列。

需要补充的一点是，虽然这里我采用编码的形式来进行状态的描述，但是实际上在程序内部是用0123456789AB（A为10的16进制表示方法，B为11的16进制表示方法）来进行存储，0与A对应，1与C对应，2与E对应，依次类推。这么做的目的只是为了方便程序的运算，减少代码量与计算量。

作者: 唐龙3bf 时间: 2018-3-16 12:33:15

本帖最后由唐龙3bf 于 2018-3-16 18:24 编辑

四、状态的产生

4.1.所有状态的产生
如何得到所有的序列呢，最简单的办法就是根据已知序列生成下一个序列。假设序列的长度是5，那么我们就可以按照12345-12354-12435-12453-……-54321的顺序生成所有的序列。
根据已知序列生成下一个序列的方法在<algorithm>中有现成的函数next_permutation()。其具体实现方式如下：
（以下内容摘自侯捷的《STL源码剖析》）

next_permutation，首先，从尾端开始往前寻找两个相邻元素，令第一元素为*i，第二元素为*ii，且满足*i < *ii，找到这样一组相邻元素后，再从最尾端开始往前检验，找出第一个大于*i的元素，令为*j，将i，j元素对调，再将ii之后的所有元素颠倒排列，此即所求之“下一个”排列组合。

只需要把“ACEGIKMOQSWY”这个状态放进去，然后不断的调用next_permutation函数就可以得到所有的序列了。

作者: 唐龙3bf 时间: 2018-3-16 12:35:24

本帖最后由唐龙3bf 于 2019-1-2 16:02 编辑

4.2.奇状态的生成
只想要研究其中的奇状态，怎么办呢，最容易想到的方法就是：生成一个，判断一个。这里给出逆序对的定义：已知序列an，如果有1<=i<j<=n，并且ai>aj，那么ai和aj就是一对逆序对。
如果一个序列里存在奇数个逆序对，那么它就是奇序列，如果一个序列里存在偶数个逆序对，那么它就是偶序列，这里和我们在魔方里的定义是同一的。至于为什么吧，其实并不是什么巧合啦，只需要简单思考一下就可以找到两者之间的关系。那么我们只需要验证一下生成的序列的奇偶性，就确定了这个序列所对应的状态的奇偶性。

这里还是拿刚刚的打乱F2 D' U2 L2 D2 B2 D2 U' B' R2 U B' R' F' D' F L' B R'F为例，统计序列WCEGOQAYMIKS中的逆序对的数量：
以W开始的逆序对有W-C，W-F，W-G，W-O，W-Q，W-A，W-M，W-I，W-K，W-S，共10对；
以C开始的逆序对有C-A，共1对；
以E开始的逆序对有E-A，共1对；
………………
以K开始的逆序对共0对；
总逆序对数量：10+1+1+1+4+4+0+4+2+0+0+0=27为奇数，所以此状态为奇状态。

作者: 唐龙3bf 时间: 2018-3-16 12:36:51

本帖最后由唐龙3bf 于 2018-3-16 17:58 编辑

五、编码长度的计算

这个问题是最简单的，虽然编写过程中出现过错误，但是它确实是很好理解的，与我们实际盲拧过程中的编码过程是完全相同的。
我总共统计了四种情况下的编码长度，分别为：全奇偶，固定奇偶，带缓冲块的反编法（A-C反编，A-G反编等），不带缓冲块的反编法（C-E反编，M-X反编等）。
需要说明的一点是UF缓冲与DF缓冲并无本质区别，A-C反编与A-G反编并无本质区别，C-E反编与M-X反编并无本质区别，固定奇偶选择的不同位置也没有本质区别。
于是，缓冲块我选择的是A，固定奇偶我放到了C的位置，带缓冲的反编法我选择的是A-C反编，不带缓冲的反编法我选择的是C-E反编，这里只是为了方便程序的计算。

作者: 唐龙3bf 时间: 2018-3-16 12:39:19

本帖最后由唐龙3bf 于 2018-3-16 17:59 编辑

六、统计结果

挂机了一个小时左右，可以得到如下的统计结果：

全奇偶.png

附件: 全奇偶.png (2018-3-16 12:38:36, 14.5 KB) / 下载次数 124
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0MTg4fGU0YTRmYTQ5fDE3Mzk3MDQyMDN8MHww

附件: 固定奇偶.png (2018-3-16 12:38:35, 15.27 KB) / 下载次数 122
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0MTg3fDUxMzI3NGI4fDE3Mzk3MDQyMDN8MHww

附件: CE反编.png (2018-3-16 12:38:35, 15.77 KB) / 下载次数 121
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0MTg2fGFkZWMwMTE1fDE3Mzk3MDQyMDN8MHww

附件: AC反编.png (2018-3-16 12:38:34, 16.41 KB) / 下载次数 112
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=MjY0MTg1fDE2YTNkNjA4fDE3Mzk3MDQyMDN8MHww

作者: 唐龙3bf 时间: 2018-3-16 12:41:13

本帖最后由唐龙3bf 于 2018-3-16 18:26 编辑

七、分析

从统计结果来看，A-C反编与C-E反编并无本质区别。在勺子的对于反编法的讨论中给我的感觉是A-C反编比C-E反编是更占优的，毕竟在实际的编码过程中A-C反编绝对不会增加编码的长度。那么为什么统计结果完全相同呢？
理由很简单，当我们对A-C两个编码进行反编的时候，实质上就是交换了编码前A与C的位置，这样魔方就从奇状态转变成了偶状态。C-E反编同理。所以，A-C反编与C-E反编以及M-X反编还有A-G反编，各种各样的反编只不过是采用了不同的方式把魔方从奇状态转换到偶状态，而且一定是一一对应的。那么，编码长度的分布以及平均编码长度一定是完全相同的。
我们之前所说的C-E反编有一定概率会增加一组编码，有一定概率会减少两组编码。但是，这种对比毫无意义，因为我们在进行对比的时候都是针对于某一个固定的状态来说的，如果把眼光放的更长远一点，考虑到所有的情况，C-E反编和A-C反编并无本质区别。

（我早就该考虑到的，那样的话可以减少一半的计算量和至少50行的代码。。。）

建议：对于角块DBL缓冲的选手，如果M-X已经在原位可以考虑不采用反编法，而是采用固定奇偶，这样也是会减少一组编码的。

作者: 唐龙3bf 时间: 2018-3-16 12:43:36

本帖最后由唐龙3bf 于 2018-3-16 18:00 编辑

八、结论

采用反编法平均会比固定奇偶的方法少0.3组编码！
采用反编法平均会比固定奇偶的方法少0.3组编码！！
采用反编法平均会比固定奇偶的方法少0.3组编码！！！

作者: 唐龙3bf 时间: 2018-3-16 12:44:42

吐槽：排版好麻烦，晚上再弄吧。

作者: 唐龙3bf 时间: 2018-3-16 12:45:21

占楼备用占楼备用

作者: 勺子 时间: 2018-3-16 14:53:52

本帖最后由勺子于 2018-3-16 15:19 编辑

   非常感谢唐龙魔友帮忙做了一直想要做的验证。后面我用excel自己又统计了一些概率。

   假设我们将全奇偶方法叫做【一】，固定奇偶方法叫做【二】，AC反编叫做【三】，CE反编叫做【四】。平均编码长度唐龙大佬已经给出了，这里直接给出一些其他结论，有问题的朋友可以来管我要计算这些概率的表格文件。

1. 三比二少的概率为31%，四比二少的概率为40%
   就是说带奇偶的反编比常规法少的概率为31%，而不带奇偶的反编比常规法少的概率为40%。（这条结论最反常识，我也没太想明白原因，欢迎大家讨论。）

2. 三和一相同的概率为49%，四和一相同的概率为49%
   就是说三和四两种反编法，和全奇偶方法长度相同的概率为49%

3. 四比一多2组的概率为0.75%，四比一少1组的概率也为0.75%。
   这个就是我的反编法帖子里面例1.3和1.6出现的极端情况，正常情况下反编法不可能比全奇偶方法少一组，也不可能多两组。但是不带奇偶的反编法可能会出现这种情况，因为会出现CE在互换位置（少一组）或是CE在原位置（多两组）的情况，不过其概率极低。
   这个概率其实也可以用排列组合来计算。比如确定奇偶状态存在，并且C在C位置，E在E位置的情况下，剩下10个棱块的位置排列数是10!/2，而全部棱块偶位置状态的排列数是12!/2，这两个数字相除就是1/(12*11) = 0.75%

作者: 天方魔 时间: 2018-3-16 15:36:35

先赞！！能算出来棱块的平均组数！非常有用！

作者: 天方魔 时间: 2018-3-16 17:42:36

勺子发表于 2018-3-16 14:53
非常感谢唐龙魔友帮忙做了一直想要做的验证。后面我用excel自己又统计了一些概率。

假设我 ...

从概率的角度上说多百分之一都算是有优势吧？

作者: 勺子 时间: 2018-3-16 17:44:04

天方魔发表于 2018-3-16 17:42
从概率的角度上说多百分之一都算是有优势吧？

对的，但是有0.75%的概率少一组公式，也有0.75%的概率多两条，所以可以认为扯平了。

作者: gbjmqh 时间: 2018-3-17 12:44:14

什么东东看了半天没看明白这是盲拧吗

作者: cad 时间: 2018-3-17 16:05:43

赞

作者: 天方魔 时间: 2018-3-18 12:29:57

勺子发表于 2018-3-16 17:44
对的，但是有0.75%的概率少一组公式，也有0.75%的概率多两条，所以可以认为扯平了。

如果都是百分之五十呢。。。

作者: 勺子 时间: 2018-3-18 14:39:37

天方魔发表于 2018-3-18 12:29
如果都是百分之五十呢。。。

呃，之前没明白你什么意思，50%肯定是很高的概率了，所以说反编法很有优势啊。

作者: 天方魔 时间: 2018-3-18 18:06:48

勺子发表于 2018-3-18 14:39
呃，之前没明白你什么意思，50%肯定是很高的概率了，所以说反编法很有优势啊。

我是说如果少两组和多两组的概率都是百分之五十。( ?° ?? ?°)?你还用吗？

作者: 勺子 时间: 2018-3-19 08:50:35

天方魔发表于 2018-3-18 18:06
我是说如果少两组和多两组的概率都是百分之五十。( ?° ?? ?°)?你还用吗？

我觉得在盲拧这个不合理的项目设定下，要用的。。。如果22左右的水平，用了这个，碰上少两组极有可能WR啊

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)