python解决开盲盒问题

发表于 更新于 分类于

这个问题是某天我们年级的一位同学提出的，感觉很有意思，就在这里记录一下。

本题算是数学方法应用在生活中的一个小例子了。

一、问题描述

开盲盒问题：现在有 12 个盒子，里面分别装了物品A-L。每个盒子都装有一个物品；每个物品都装在一个盒子中。

在开盲盒之前，有一次透视机会，可以知道其中任意一个盒子里是什么（例如开了 3 号盒子可以得知里面是物品 C）。

现在每个盒子有3次提示的机会，提示内容分别是“该盒子中不是 X”（X是物品编号），同一个盒子中的3次提示内容不会重复，但盒子之间的提示是会重复的。此外，还有额外的6次机会，可以随机选 6个盒子，得到第四条提示。

例如：目前开了1个盒子，并对另外两个盒子的物品进行了提示，情况如下：

盒子编号 1 2 3 4 5 6 7 8 9 10 11 12
第一次提示 非 A 非 A 是 C
第二次提示 非 B 非 D
第三次提示 非 C 非 E
额外的提示 非 K 非 L

编写程序，当输入所有已知条件时，输出物品A-L在每个盒子里的概率。

二、思路与代码

（一）物品位置状态表的获取

题干中的表格给了我们很大的提示，我们也可以建立一张表来展示各个物品在不同盒子中的概率。如下表所示，我们建立了一个12x12的状态表，其中每一行代表一个物品（A-L对应第0-11行），每一列代表一个盒子（1-12号盒子对应第0-11列）。

我们定义数字 1代表物品可能在盒子中，0代表物品不可能在盒子中。因此根据题目已知条件，这样的表格如下：

盒子编号 1 2 3 4 5 6 7 8 9 10 11 12
A 0 0 0 1 1 1 1 1 1 1 1 1
B 0 1 0 1 1 1 1 1 1 1 1 1
C 0 0 1 0 0 0 0 0 0 0 0 0
D 1 0 0 1 1 1 1 1 1 1 1 1
E 1 0 0 1 1 1 1 1 1 1 1 1
F 1 1 0 1 1 1 1 1 1 1 1 1
G 1 1 0 1 1 1 1 1 1 1 1 1
H 1 1 0 1 1 1 1 1 1 1 1 1
I 1 1 0 1 1 1 1 1 1 1 1 1
J 1 1 0 1 1 1 1 1 1 1 1 1
K 0 1 0 1 1 1 1 1 1 1 1 1
L 1 0 0 1 1 1 1 1 1 1 1 1

通过代码得到上面的表格并不难，即使输入条件有变化，我们也可以根据输入条件的不同进行改变。

下面是我们的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import numpy as np

# 建立一个12x12的状态表
# 每一行代表一个物品（A-L对应第0-11行）
# 每一列代表一个盒子（1-12号盒子对应第0-11列）
# 1代表物品可能在盒子中，0代表物品不可能在盒子中
status_table = np.ones([12,12])

#print(status_table)

# 在一次透视机会中看到的盒子与内容
#----------------------------------#
# 此处根据看到的具体情况进行赋值   #
#----------------------------------#
inspect_box  = 2 # 3号盒子对应的列下标
inspect_item = 2 # 物品C对应的行下标

# 更新状态表
status_table[inspect_item,:] = 0 # 这个物品在其他盒子中不可能出现，因此状态赋值为0
status_table[:,inspect_box]  = 0 # 这个盒子中也不会有其他物品，因此状态赋值为0
status_table[inspect_item,inspect_box] = 1 # 只有这个物品一定存在，因此赋值为1


# 通过对其他盒子的提示（包括6次额外机会），得到的提示内容
#----------------------------------#
# 此处根据看到的具体情况进行赋值   #
#----------------------------------#
tips_table=[
        [0,1,2,10], # 1号盒子中不可能出现的物品下标
        [0,3,4,11], # 2号盒子中不可能出现的物品下标
        [], # 3号盒子中不可能出现的物品下标
        [], # 4号盒子中不可能出现的物品下标
        [], # 5号盒子中不可能出现的物品下标
        [], # 6号盒子中不可能出现的物品下标
        [], # 7号盒子中不可能出现的物品下标
        [], # 8号盒子中不可能出现的物品下标
        [], # 9号盒子中不可能出现的物品下标
        [], # 10号盒子中不可能出现的物品下标
        [], # 11号盒子中不可能出现的物品下标
        [], # 12号盒子中不可能出现的物品下标
        ]
# 更新状态表
for i in range(12):
    # i 是盒子的下标。
    # 下面读取tips_table，获取盒子中不可能出现的物品下标
    for j in tips_table[i]:
        # 更新状态表
        status_table[j][i] = 0

# 打印状态表
print("状态表=")
print(status_table)

# 打印每个物品可能出现的盒子编号（盒子编号=盒子下标+1）
for i in range(12):
    status_array = status_table[i]
    boxes = []
    for j in range(len(status_array)):
        if(status_array[j]==1):boxes.append(j+1)
    print("物品{}可能出现在盒子{}中".format(chr(i+65),boxes))

输入条件在代码的 inspect_box, inspect_item, tips_table 三个变量中定义（见上述代码“此处根据看到的具体情况进行赋值”的提示语句）。

  • inspect_box ： 在一次透视机会中，查看的盒子的下标。盒子的下标等于盒子编号减1。
  • inspect_item ：在一次透视机会中，看到的物品的下标。物品编号A-L分别对应物品下标0-11。
  • tips_table ：通过每个盒子的3次提示机会，和6次随机盒子的提示机会，得到的所有信息。这些信息按二维数组进行组织（见代码），其中外层数组的下标对应盒子下标，内层数组的元素代表不会出现的物品的下标。内层数组可以是空数组。

（二）概率值的计算

上面得到的仅仅是一个状态表。我们需要知道每个物品出现在各个盒子中的概率。而这个概率，可以用线性规划的方法解出来。

具体来说，当我们把12x12的状态表变成12x12的概率表以后，表格中的每个格子就变成了对应物品在对应盒子中出现的概率。一共144个格子（144个待求解概率），因此线性规划的变量个数为144个。

除此之外，我们需要明确两点事实：

  • 任意一个盒子中，各个物品出现概率的总和为1。（也就是说对于一个特定的盒子，从物品A到物品L，不论每个物品各自出现的概率有多大，这些物品出现概率的总和一定是1）
  • 任意一个物品，出现在每个盒子中的概率的总和为1。（也就是说对于一个特定物品，它在盒子1到盒子12中出现的概率值加在一起也是1）

放到12x12的概率表上，就是这个概率表的每一行的元素总和全为1，每一列的元素总和也全为1。由此可以得到12×12=24个约束条件函数。

此外，每个变量也有自己的边界条件。概率的取值范围为 $\in[0,1]$ ，然而对于不可能出现的物品来说，概率值一定为0。这是另外144个条件。

我们的目标函数是概率总和最大；然而对于这个问题来说，目标函数是什么其实无所谓，因为上面的这些约束条件足以求出我们所要的结果。

求解线性规划问题的方法有很多，此处我们使用scipy进行求解

参考： 使用Python和SciPy解决线性规划问题

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# 这段代码需要接在上面那段代码的后面
# 因为需要用到status_table这个变量，以确定概率值的边界条件
from scipy.optimize import linprog
c = -np.ones(144) # 目标函数的系数向量。总共144个变量（12x12），因此向量长度为144.
A_eq = [] # 等式约束条件的系数矩阵。下面对这个系数矩阵进行赋值
# 矩阵每行的概率总和均为1，总共12个方程
for i in range(12):
    a_eq = np.zeros(144)
    a_eq[i*12:(i+1)*12]=1
    A_eq.append(a_eq)
# 矩阵每列的概率总和均为1，总共12个方程
for j in range(12):
    a_eq = np.zeros(144)
    for i in range(12): a_eq[i*12+j]=1
    A_eq.append(a_eq)
B_eq = np.ones(24) # 等式约束条件的常数项。总共24个方程，因此向量长度为24

# 变量的边界条件
# 其中，状态表的状态值=0的位置，对应边界条件为p=0
# 除此之外的位置，边界条件为 p ∈ (0,1]
p0 = (0,0)
p1 = (0,1)
bounds = []
for i in range(12):
    for j in range(12):
        if(status_table[i][j]==0):
            bounds.append(p0)
        else:
            bounds.append(p1)

# 计算线性规划的结果
result = linprog(c,A_eq=A_eq,b_eq=B_eq,bounds=bounds)
x = np.array(result.x)

# 打印结果
print("Prob table=")
print("\t".join(["Item","1","2","3","4","5","6","7","8","9","10","11","12"]))
for i in range(12):
    print(chr(65+i),end="\t")
    for j in range(12):
        print("%.4f"%x[i*12+j],end="\t")
    print()

三、代码输出：

全部的代码输出如下，其中程序首先输出了12×12状态表，并打印出各个物品可能出现在哪些盒子中，最后输出了12×12的概率表，从概率表中我们可以选择每个物品出现概率最大的盒子，以确定要开哪一个盲盒。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
状态表=
[[0. 0. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [0. 1. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [0. 0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [1. 0. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 0. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 1. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [0. 1. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]
 [1. 0. 0. 1. 1. 1. 1. 1. 1. 1. 1. 1.]]
物品A可能出现在盒子[4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品B可能出现在盒子[2, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品C可能出现在盒子[3]中
物品D可能出现在盒子[1, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品E可能出现在盒子[1, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品F可能出现在盒子[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品G可能出现在盒子[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品H可能出现在盒子[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品I可能出现在盒子[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品J可能出现在盒子[1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品K可能出现在盒子[2, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
物品L可能出现在盒子[1, 4, 5, 6, 7, 8, 9, 10, 11, 12]中
D:\linux\py\开盲盒问题.py:128: OptimizeWarning: A_eq does not appear to be of full row rank. To improve performance, check the problem formulation for redundant equality constraints.
  result = linprog(c,A_eq=A_eq,b_eq=B_eq,bounds=bounds)
Prob table=
Item    1       2       3       4       5       6       7       8       9       10      11      12
A       0.0000  0.0000  0.0000  0.1111  0.1111  0.1111  0.1111  0.1111  0.1111  0.1111  0.1111  0.1111
B       0.0000  0.1563  0.0000  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937
C       0.0000  0.0000  1.0000  0.0000  0.0000  0.0000  0.0000  0.0000  0.0000  0.0000  0.0000  0.0000
D       0.1371  0.0000  0.0000  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959
E       0.1371  0.0000  0.0000  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959
F       0.1177  0.1375  0.0000  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828
G       0.1177  0.1375  0.0000  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828
H       0.1177  0.1375  0.0000  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828
I       0.1177  0.1375  0.0000  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828
J       0.1177  0.1375  0.0000  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828  0.0828
K       0.0000  0.1563  0.0000  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937  0.0937
L       0.1371  0.0000  0.0000  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959  0.0959

由于已知条件的限制，我们得到的概率表中不同盒子之间的概率差异还是有点小，不足以判断一个物品最有可能出现在哪个盒子中。当已知条件足够多（例如使用完全部36次提示机会和6次额外机会），则得到的概率值会更加精确。