猜排列问题

wayne

mathe猜对之前Fans不洗牌。

也即是说，mathe猜的一直是同一个排列。
KeyTo9_Fans 发表于 2012-4-2 12:39

嗯，是我粗糙了点。
我其实是对 mathe 的策略 存在疑问。
即，mathe如何才能利用 Fans 反馈的猜对k张牌了 这种信息 作出最佳的策略

wayne

提炼一下问题：
mathe前n-1次，依次猜对了，a1,a2,a3, an-1张牌，那么，猜第n次的时候，mathe该如何做？
如果利用不了前面已有的猜测信息，那么无异于盲猜，无异于Fans洗牌了，于是答案就是52! 了

期待mathe现身ing。。。

hujunhua

把11#的表看懂就知道了。看来我楼上的解释表述还不够明白。

以第1猜为例。设牌张数为n, 将mathe首猜排列记为123 ...n, 将其它的n!-1个可能排列分别与首猜排列逐位比对，若有k位相同（k=0, 1, 2, ..., n-2, n)就归入第k类。当Fans提示猜了k个数时，除了第k 类中的排列，其它类都可以舍弃了。
接下来的甄别规则是类似的。

hujunhua

我在按上述方法手工计算n=4 张牌的进程表。

我办公电脑坏了，要不可以用Mathematica8编程计算。即使不编完整的程序，简单地使用Mathematica8的排列组合函数也能节省不少时间，少出错误。

hujunhua

现在已经发现，对于n=4张牌，如果G1=0(即首猜全错)，那么mathe的第2猜需要策略。第0类={2143  2341  2413  3142  3412  3421  4123  4312  4321}, 猜2143，3412或者4321较劣，选其它6个较优。

hujunhua

n=4的进程表已经较大，只好拆开了，表1是第1猜及根据提示所作的取舍判断。
表1

A0	1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321
G1	4	2	1	0
A1	1234	1243  1324  1432 2134  3214  4231	1342  1423  2314  2431 3124  3241  4132  4213	2143  2341  2413   3142   3412 3421  4123  4312   4321

表2 G1=2的后继进程

G1	4	2
A1	1234	1243  1324  1432  2134  3214  4231
	G2	4	2	1					0
	A2	1243	/	1324, 1432, 3214, 4231					2134
			G3	4	2	1		0	4
			A3	1324	/	1432 3214		4231	2134
					G4	4	0	4
					A4	1432	3214	4231
						A5	3214

表3 G1=1的后继进程

G1	4	1
A1	1234	1342  1423  2314  2431  3124  3241  4132   4213
	G2	4	2	1								0
	A2	1342	/	1423  3241  4132  2314								4213 2431 3124
			G3	4	2	1	0					4	2	1	0
			A3	1423	/	/	3241  4132  2314					4213	/	/	2431 3124
						G4	4	2	1	0					4	0
						A4	3241	/	/	4123  2314					2431	3124
									G5	4	0					4
									A5	4123	2314					3124
										A6	2314

表4 G1=0的后继进程(第2猜以蓝色的选择，即选猜2341较优）

G1	4	0
A1	1234	2143  2341  2413  3142  3412  3421  4123  4312 4321
	G2	4	2						1					0
	A2	2143	2341  2413  3142  4123						/					3412  3421  4312  4321
		G3	4	2	1			0						4	2			1	0
		A3	2341	/	2413 3142			4123						3412	3421  4312			/	4321
				G4	4		0	4							4	0			4
				A4	2413		3142	4123							3421	4312			4321
					A5		3142									4312
	A2	2341	2143  4321						2413  3142  3421  4312					3412  4123
		G3	4			0			4	2	1		0	4			0
		A3	2143			4321			2413	/	3421  4312		3142	3412			4123
			G4			4					4	0	4				4
			A4			4321					3421	4312	3142				4123
											A5	4312

wayne

哇
老大还不睡啊

hujunhua

根据表1至表4统计，P(1)=1/4!, P(2)=3/4!, P(3)=7/4!, P(4)=8/4!, P(5)=4/4!, P(6)=1/4!
所以E(4,k)=∑kP(k)=86/24(按较优策略统计的结果)

若按较劣的策略，则P(3)=6/4!, P(4)=8/4!, P(5)=5/4!, P(6)=1/4!
所以E(4,k)=∑kP(k)=88/24

统计出来再睡。表编辑了半天也没搞好，看来得等郭老板帮助了。

hujunhua

统计P (k)时数表中Gk=4的频数，再除以4!就行了。

hujunhua

猜牌进程中，猜对的牌数并不是递增的，而是通过缩减Ak各类中的排列数达到目标的。猜对的牌数是反复振荡的，有时上一次猜对零张，但第0类中只有一个排列了，再一次就可以直接猜中。