猜排列问题

mathe

牌的数目少的时候穷举即可。但是这个在牌的数目多了就不行了。
我倒是觉得可以随机排列，选择大概nlog(n)次后，根据概率，每次位置对的牌的数目很少，特别的，大概有exp(-1)的比例全部猜错（它们均淘汰了很多牌的位置），利用这种信息可以淘汰大量情况，然后再可以有针对性的出方案

hujunhua

KeyTo9-Fans这题出得有点意思。我感兴趣的是分布函数P(n, k)是否为某种已知的类型.

频数N(n,k)		k
		1	2	3	4	5	6	7	8
n	1	1
	2	1	1
	3	1	2	2	1
	4	1	3	7	8	4	1
	5
	6

每一行最右端都是1吗，即运气最差，需要次数最多的频数仅为1？

hujunhua

1. n = Input["请输入牌张数"];
   
2. A = Delete[Permutations[Range[n]], 1]; "产生n阶全排列集，并去掉第1个元素，因为第1个是12...n，为选猜排列";
   
3. A = GatherBy[A, PermutationLength]; k = 1; "将剩下的排列按与12...n的对应相同的牌数进行分组，这是第1次分组";
   
4. Fb = {1}; "分布初值";
   
5. While[Length[A] > 0, ++k; "当分组表非空时进行第k次猜牌，分组表为空时结束";
   
6. Fb = AppendTo[Fb, Length[A]]; "上次所分组数即是第k次猜中的频数，加入分布表中";
   
7. A = # /. Thread[#[[1]]->Range[n]] &/@A; "将每个组的第1个排列置为12...n,并将组内其它排列作相应的调换";
   
8. A = Cases[Delete[#, 1] &/@A, Except[{}]]; "去掉每个组的第1个排列，并去掉由此产生的空集";
   
9. A = Flatten[GatherBy[#, PermutationLength] &/@A, 1]]; "将每个组的剩余排列按与12...n的对应相同的牌数进行分组，然后抹掉上一层组";
   
10. Print["--------"]
    
11. Print["牌张数n=", n, ",最多次数=", k, ",频数分布为", Fb]
    
12. Print["期望次数为", N[Range[k].Fb/Factorial[n]]]
    

复制代码

每当KeyTo9-Fans告诉Mathe猜对的牌数时，Mathe就作一次判断，剔除排列集中的不可能者，然后在剩下的可能排列中选第1个猜——这时选哪一个猜可能对剩余集的分解是不同的，而且第1个往往不会产生最均分组（均则优）。但是这种精细的策略对于结果的影响不大，所以为了简化程序，Mathe就选第一个。

hujunhua

用手算的已知结果检验一下程序。
n=1，2，3，4时，检验结果

1. 牌张数n=1,最多次数=1,频数分布为{1}
   
2. 期望次数为1.
   

复制代码

1. 牌张数n=2,最多次数=2,频数分布为{1,1}
   
2. 期望次数为1.5
   

复制代码

1. 牌张数n=3,最多次数=4,频数分布为{1,2,2,1}
   
2. 期望次数为2.5
   

复制代码

1. 牌张数n=4,最多次数=6,频数分布为{1,3,6,8,5,1}
   
2. 期望次数为3.66667
   

复制代码

程序应该没什么问题

hujunhua

可以计算一下较大的数了：

1. 牌张数n=5,最多次数=8,频数分布为{1,4,13,30,46,19,5,2}
   
2. 期望次数为4.69167
   

复制代码

1. 牌张数n=6,最多次数=11,频数分布为{1,5,21,72,162,239,152,47,17,3,1}
   
2. 期望次数为5.88889
   

复制代码

1. 牌张数n=7,最多次数=12,频数分布为{1,6,30,125,401,980,1536,1343,513,91,11,3}
   
2. 期望次数为7.07698
   

复制代码

1. 牌张数n=8,最多次数=14,频数分布为{1,7,41,203,796,2589,6466,11028,11110,6086,1676,281,32,4}
   
2. 期望次数为8.36012
   

复制代码

n=9先放着，别把机子算死了，丢了小数据划不来。

hujunhua

1. 牌张数n=9,最多次数=20,频数分布为{1,8,53,300,1410,5594,18184,46623,84433,99460,70393,28932,6513,829,106,31,6,2,1,1} 期望次数为9.69137

复制代码

hujunhua

1. 牌张数n=10,最多次数=20,频数分布为{1,9,67,427,2288,10679,41849,137055,354588,678128,909649,819130,470281,165028,34577,4515,491,36,1,1}
   
2. 期望次数为11.1053

复制代码

wayne

新鲜出炉的呀，赞叹

hujunhua

wayne不是有台NB机子么，又精于Mathematica, 可否把这个程序改进一下，往大里算算看。
看趋势要不了nlogn这么高，貌似n 就够了。但是数据小了，不可靠。

hujunhua

10多分钟了，n=11还没有算出来。