移动数字的问题

lulijie

9个数字分布在9个格子总状态数为9的阶乘=362880种
  其中右下角为空格的总状态数为8的阶乘=40320种。
用(123456789) 表示以下状态              9代表空格。
        1 2 3
        4 5 6
        7 8 9
经过电脑计算，经过移动能够成为目标状态（123456789）的总数为181217（包括该目标状态）。其中每种状态都有一个最少移动步数N,经过移动N步可以达成目标状态。   
    （123456789） 的最少步数N=0
    （123459786）和（123456798）  的最少步数N=1
     最远的状态为29步，（654321897）就是其中之一。逆序状态（987654321）为28步。
     右下角为空格的最远状态为28步，（564231879）是其中之一。
     右下角为空格的各种状态最少步数都是偶数。
----------------------------------------------------------------------------------------------------------------------
        最少步数N         总状态数      右下角为空格的总状态数
           0                            1                        1
           1                            2                        0
           2                            4                        0
           3                            8                        0
           4                           16                       2                 
           5                           20                       0
           6                           39                       8
           7                           62                       0
           8                         116                     26
           9                         152                       0
          10                        286                     48
          11                        396                       0
          12                        748                   138
          13                      1024                       0
          14                      1893                   364
          15                      2512                       0  
          16                      4485                   834
          17                      5638                       0
          18                      9529                 1852
          19                    10878                       0
          20                    16993                 3337
          21                    17110                       0
          22                    23952                 4738
          23                    20224                       0
          24                    24047                 4904
          25                    15578                       0
          26                    14560                 3009
          27                      6274                       0            
          28                      3910                   854
          29                        760                       0
         总计                181217               20115

lulijie

右下角为空格的总状态数为8的阶乘=40320种。
其中经过移动最终可以变成目标状态的总数为20115种，比不能变成目标状态的总数20205稍少些，并不是各占一半。

骰迷

這...這怎麼可能？為什麼不是均等？難道魔方（不算色向）隨機裝回，能擰完的機會不是二分一？怎麼可能數量不一樣？
另外，順逆序的最遠狀態步數理應一樣的啊。123456789、987654321只是符號，無論用什麼符號代表該塊的原本位置，本質上也沒有分別。逆序的456789213需要多少步？理論上是29步的。


[ 本帖最后由 骰迷 于 2009-2-8 22:30 编辑 ]

lulijie

相信事实吧，大多数情况下直觉都是错的。

骰迷

建基"只是符號，無論用什麼符號代表該塊的原本位置，本質上也沒有分別"的理論，目標狀態跟非目標狀態的數量理應一樣。例如7、8是倒轉的，那麼所謂的＂目標狀態＂也相對的有一個＂反目標狀態＂，就是把它的78倒轉，形成反目標狀態。

lulijie

（456789213）21步

lulijie

右下角为空格的总状态数为8的阶乘=40320种。
其中电脑计算出的经过移动最终可以变成目标状态的总数为20115种，距一半还差45种。
我也觉得应该是一半的可能性大，我再仔细审查一下程序设计上是否有不当之处。

oboe

允许正反不一样吧。

在大量测试 的时候， 出现不均等的机会确实会狠大。

lulijie

设计上不是采取随机状态，而是从目标状态经过移动，得到新的状态，再从新的状态，移动得到再新的状态，一步步进行下去，每次得到新的状态后要检查它们，是否之前已经出现过的，已经出现过的不再计算进去，直到不出现以前没有出现过的状态为止。最后记录下运行中算出的所有状态，进行统计。
所以不存在大样本，概率的问题。

骰迷

那麼，即是說：目標狀態＋反目標狀態（注意，這不是非目標狀態，反目標狀態即是將87倒轉）＜所有狀態數
有一些狀態雖然奇偶性一樣，但不能還原？