猜排列问题

hujunhua

实现（伪）随机选猜，不再限于长猜第1个或者倒数第1个。

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

复制代码

hujunhua

4张牌的多次运行结果只有2个，与手算相同，而且第1个结果出现的频率高，第2个结果出现得较少。理论上，前者占2/3, 后者占1/3.

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

复制代码

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

复制代码

hujunhua

将程序放到一个For循环中，在n=5时运行1000次，并统计｛最多次数，期望次数，频数分布表｝，程序自动统计发现的最优策略和最差策略如下：
最优：{6, 538/120 = 4.48333, {1, 4, 13, 34, 54, 14}}
最差：{8, 565/120 = 4.70833, {1, 4, 13, 33, 41, 18, 8, 2}}

荼靡破晓

很难懂 俺有点

shuzimi

6# 056254628
受益匪浅

mathe

KeyTo9_Fans 发表于 2012-4-2 11:27
“mathe，你真有才，虽然猜错了50棵牌， 但猜对了第12，第34棵牌，值得鼓励，再接再厉啊”

这样的回复可 ...

感觉这个题目可以在$O(N)$复杂度内解决，而不是Fans和mathe以前猜的$O(N\log(N))$。
考虑到错位排序的占比达到了所有排序中约$1/e$
mathe可以随机给出排序，知道听到Fans说: mathe你太笨了,竟然猜对了0张
然后mathe后面继续随机出牌，但是每个位置上如果Fans给过猜对0张评价的方案就不用再试验了。
理论上听到n-1次猜对0张就可以结束游戏了。
当然这个方案到了后面可能效率会降低了，但是事实上到了后面，不是猜错0张情况的信息也很多，越到后面可取信息应该越多，所以$O(N)$以内应该可以解决。

王守恩

KeyTo9_Fans 发表于 2012-4-2 11:27
“mathe，你真有才，虽然猜错了50棵牌， 但猜对了第12，第34棵牌，值得鼓励，再接再厉啊”

这样的回复可 ...

“mathe，你真有才，虽然猜错了50棵牌， 但猜对了第12，第34棵牌，值得鼓励，再接再厉啊”
如果是这道题，51次就可以。
52棵牌一字排开，猜对的原地不动了，没猜对的往前挪一棵(跳过原地不动的)，最前面的一棵挪到最后面。

mathe

也许可以试验一下概率模型，开始n个位置选择每个数的概率都是1/n，并总是假设不同位置个数字的概率分布是独立的。然后mathe每次随机选择一个概率非零的排列(也可以尝试选择概率最高的排列)，然后根据Fans的反馈结果修订各数字的概率。唯一需要注意的是如果选择某个高概率方案后Fans如果反馈多数命中，会再次提升这个选择的概率，而我们必须避免重复选择相同的模式(毫无意义的选择)。也许可以以一定比例组合最大概率选择和随机选择会有不错的结果

mathe

从另外一个角度，每次选择非零的低概率方案可能也不错，因为会有较高概率准确淘汰非法方案

manthanein

这个问题还没完全解决吗？感觉很像猜数字游戏。
不同的是猜数字游戏会说明有几个数字猜对也位置也对上，有几个数字猜对了但位置没对上。