魔方吧·中文魔方俱乐部

标题: 想计算一下打乱后角块在原位的概率问题 [打印本页]

作者: xpboy 时间: 2009-8-29 10:36:32 标题: 想计算一下打乱后角块在原位的概率问题

这个跟盲拧关系比较大吧，想请乌木老师以及各位数学高手帮忙计算一下，呵呵

想计算的如下：三阶魔方打乱后，所有角块都不在原位的概率；1个角块在原位的概率；2~6个角块在原位的概率；

还有小循环的概率：一次循环完成所有角块的概率；2~4个角块小循环的概率。

因为现在正在研究彳亍法编码，想大概了解一下一般需要多少步的编码，所有有如上问题，多谢！

作者: pengw 时间: 2009-8-29 12:59:27

T1=M/2*A/2*2=MA/2
T2=M/2
T2/T1=1/A

A=8！*3^7
M=12！*2^11

角块不变的状态与总状态数之比：1/8！*3^7，其数量：M（A-1）/2

----------------

楼主的问题并不严格，我只是假定所有角块在原位保持原方向，限讨论纯色三阶，至于1-6个，以此类推

[ 本帖最后由 pengw 于 2009-8-29 20:52 编辑 ]

作者: pengw 时间: 2009-8-29 13:18:53

不妨也给出楼主想要的完整答案：((8-n)!/2*3^(8-n-1)*c(8,n)*12!*2^11)/(8!/2*3^7*12!*2^11),1<=n<6

=(8-n)!*c(8,n)/(8!*3^n),1<=n<6

其中，c(8,n)代表8个元素任取n个的组合数

------------

当然,这里假设在原位原向,否则还要X上3^n

[ 本帖最后由 pengw 于 2009-8-29 22:23 编辑 ]

作者: 乌木 时间: 2009-8-29 20:53:44

“三阶魔方打乱后，所有角块都不在原位的概率”，约定，中心块不变；一个角块原地的色向变化不计；角块的位置变化之中相当于单单交换两个角块的位置的状态也计入（因为还有棱块的位置变化可以配合这种状态使之可能）。
8个角块在8个位置上的变化数为8！。
一个角块不在原位的情况有7种，每一种都含有其余7个角块在7个位置上的位置变化数7！，总共为7×7！种。
两者之比为7×7！/ 8！＝7 / 8 。
8个角块应该同等，每个角块都有7 / 8的概率不在原位，它们都不在原位的概率是不是
（7 / 8）^ 8≈0.34 ，对吗？
我对这种概率问题很怕，上面的中间结果“7 / 8”含有许多别的角块在原位的情况，对吗？我却不考虑，可以吗？我这样只抓每个角块不在原位的概率，把它们看作一个个独立事件，让它们同时发生，求得约0.34，有问题吗？我实在没把握。大家指点为要。

[ 本帖最后由乌木于 2009-8-29 21:27 编辑 ]

作者: pengw 时间: 2009-8-29 22:11:23

乌老可能应该考虑到：
1。在原位的块可能有不同的组合，如二个在原位有28种组合
2。在原位的块可能有不同色向，这个不用我说
3。块的数量与扰动之间的关联，如大于4个块在原位只有一种扰动可能

计算方法：满足条件的状态与总状态数之比，事实上，我的计算都忽略了某些扰动情况下，如4个在原位可能变成5个在原位，所以不完全正确

[ 本帖最后由 pengw 于 2009-8-29 22:31 编辑 ]

作者: 乌木 时间: 2009-8-29 22:38:03 标题: 回复 5# 的帖子

我4楼仅仅试着算算“三阶魔方打乱后，所有角块都不在原位的概率”，且约定了三点，其中约定不计色向变化是因为此题只问“角块都不在原位…………”，如果要考虑色向变化数，也许算有关概率时色向变化数会抵消吧？
至于角块位置上的扰动问题，4楼我是推给棱块的位置去调节的，凡是角块有扰动，那就让棱块也扰动好了，反正此题只讲角块的位置变化问题。（有如PLL公式中，单看角块，不少公式是角块两交换来着，但是有棱块的两交换调节着，完全正常。）
你说“1。在原位的块可能有不同的组合，如二个在原位有28种组合”，这我就不熟悉了，暂时也不去管这些了，我想，偷懒一下，避开在原位的角块的组合不组合的问题，因为此题是问“所有角块都不在原位的概率”。不知4楼这样算对吗？（我吃不准的问题已在4楼问了。）

[ 本帖最后由乌木于 2009-8-29 23:14 编辑 ]

作者: 乌木 时间: 2009-8-30 11:04:01

“1个角块在原位的概率”是指“只有一个角块在原位的概率”吧？
仍约定参照中心块；角块的色向变化不计；允许单单两个角块交换位置性质的位置状态。
一角在位，其余7角的位置本来可以有7！种变化数；现在要扣除7！之中有的角块也在位的情况数，这涉及7块之中选1个、2个、3个……等等的组合数，我是搅不清了。还是看看7个角块都不在位的概率吧。
7个块中的某一个不在位的情况有6种，每一种都含有其余6个角块在6个位置上的位置变化数6！，总共为6×6！种。
7个块中的某一个不在位的概率就是6×6！/ 7！＝6 / 7 。
所以，7个块都不在位的概率为（6 / 7）^ 7 。
这是8个角之中1个在位7个都不在位的概率；8个角分别单单一个在位的状态数之和的概率，是8个（6 / 7）^ 7 相加，不是相乘，因为这8种情况不是同时发生的，对吗？
所以，“只有一个角块在原位的概率”为 8×（6 / 7）^ 7 。
有问题了，概率大于1了，可以乘以8吗？
望行家指点。

[ 本帖最后由乌木于 2009-8-30 11:28 编辑 ]

作者: xpboy 时间: 2009-8-30 12:55:33

我的前提确实如乌木老师所说，不考虑色相，只考虑位置

想了半天没想到合适的计算方法，我就编了段程序穷举了一下状态数 -_-!

角块变化数为8!=40320种
全不在原位的状态有 14833种，大概为36.79%

一个角块在原地，剩下7个角块不在原地的状态有1854种，那么对应状态数*8=14832种概率 36.79%

两个角块在原地，剩下6个角块不在原地的状态有265种对应状态数*C(2,8)=265*28=7420 种概率 18.4%

三个角块在原地，剩下5个角块不在原地的状态有44种对应状态数*C(3,8) =44*56=2464 概率 6.11%

四个角块在原地，剩下4个角块不在原地的状态有9种对应状态数*C(4,8) =9*70=630 概率 1.56%

五个角块在原地，剩下3个角块不在原地的状态有2种对应状态数*C(5,8) =2*56=112 概率 0.28%

六个角块在原地，剩下2个角块不在原地的状态有1种对应状态数*C(6,8) =1*28=28 概率 0.07%
全部在原地， 1种概率 0.0025%

以上相加正好是40320种状态

小循环数目的计算方法还没想出来…………

附上我的html源文件

[ 本帖最后由 xpboy 于 2009-8-30 13:48 编辑 ]

附件: cube_2.zip (2009-8-30 12:55:33, 676 Bytes) / 下载次数 12
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NjY1OTB8ZDEyYTMwOGR8MTcxNTM2NzYxMXwwfDA%3D

作者: 乌木 时间: 2009-8-30 15:11:57

7楼计算显然不对，试试重新算。

一个角块在位，其余7个角块中的某一个不在位的情况有6种，每一种都含有其余6个角块在6个位置上的位置变化数6！，总共为6×6！种。
7个块中的某一个不在位的概率就是6×6！/ 7！，
所以，7个块都不在位的概率为（6×6！/ 7！）^ 7 ，
相应的7个块都不在位的数目为（6×6！/ 7！）^ 7 ×7！。
一个在位的角块带上这么一大帮子，那么，8个分别在位的角块共有态数为
（6×6！/ 7！）^ 7 ×7！ ×8 ，
8个角块的所有变化数为8！，上述态数所占的分数为
（6×6！/ 7！）^ 7 ×7！ ×8 / 8！＝（6×6！/ 7！）^ 7＝（6 / 7）^ 7≈0.3399，
所以，“只有一个角块在原位的概率”为（6 / 7）^ 7≈0.3399 。

[ 本帖最后由乌木于 2009-8-30 15:15 编辑 ]

作者: 乌木 时间: 2009-8-30 15:20:04 标题: 回复 8# 的帖子

这么看来，我4楼和9楼的算法还是有问题的。

作者: pengw 时间: 2009-8-30 22:01:51

帮8楼整理出一个n个块不在原位的所有可能排列之关键计算公式，不用穷举，太费事了
-----------------------------------------------------------------------------------------------------------
F=n!*　(1+∑（（-1）^a*1/a!))，其中(a=1到a=n，n是大于或等于2的正整数，n对应不在原位的块数)
-----------------------------------------------------------------------------------------------------------
用公式F可以轻易计算出n个块匀不在原位的所有可能排列数，跟你的计算值完全一致

n=2:2!*(1-1+1/2!)=1
n=3:3!*(1-1+1/2!-1/3!)=2
n=4:4!*(1-1+1/2!-1/3!+1/4!)=9

[ 本帖最后由 pengw 于 2009-8-30 22:36 编辑 ]

作者: 乌木 时间: 2009-8-30 22:31:05 标题: 回复 11# 的帖子

真方便了！
最后一例等于9，不是44，笔误了。

作者: pengw 时间: 2009-8-30 22:38:36

是笔误了，已更正。推导过程很繁杂，就略去了。

作者: pengw 时间: 2009-8-30 23:01:10

有了11楼的公式，那么可以偿试计算三阶所有块不在原位的状态有多少

作者: xpboy 时间: 2009-8-31 23:55:23

哇，这个排列的公式居然这么复杂……太强了，这都能算出来……

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