猜排列问题

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类中只有一个排列了，再一次就可以直接猜中。