用Python计算LOL中猫咪状态数

我们知道在LOL(英雄联盟)中,猫咪是可以进入队友身体的,如果LOL再出5V5克隆模式(我猜不可能),如果某一方选了猫咪这个英雄,场面上会有多少种状态呢(不考虑死亡)?

这个问题在2019年5月猫咪刚出来的时候就在好好做人群讨论并给出了结论,只是没写成程序

答案是:1296 (可以先拉到最后)

问题数学化:

每只猫可以进入其他猫咪的身体,求(我们更关心$a_n $):

  • $n$只不同的猫咪,会有$a_n$种状态

  • $n$只相同的猫咪,会有$b_n$ 种状态

我们想要得到$a_n$ 和 $b_n$ 的表达式或者递推公式,然后写程序求 $a_n, b_n$

为了方便,我们约定 $a_0 = b_0 = 1$

问题求解:

我们可以根据能看到的猫咪数量 $r$ ,来分情况讨论,

我们先考虑相同猫咪的情况,简单一点 下面分析全错!!!

例如,如果$r=1$,那么其它猫咪都进入了某一只猫咪的身体,有 $b_{n-1}$ 种情况,类似的我们其实可以得到如下公式:

$r$ 只可见的猫,分别真实包含了 $x_1, \cdots, x_r$ 只猫,而这$x_i$ 只猫有一个在最外面,所以它的内部有 $b_{x_i - 1}$ 种可能。

$b_1 = 1, b_2 = 2$ 是显然的。我们来计算$b_3, b_4, b_5$

$3 = 1+2 = 1 \times 3$,所以

$4 = 1+3 = 2+2 = 1+1+2 = 1 \times 4$, 所以

类似的对$5$做分解可知:

代码实现:

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
#正整数拆分 n = x_1 + x_2 + ... + x_r, 且 x_i >= low
#low 表示递归的时候最小取值
#ans 保存递归得到的前部分
def naturalcut(n, r, low, ans = []):
if r <= 1:
yield ans+[n]
else:
for i in range(low, 1 + n//r):
yield from naturalcut(n-i, r-1, i, ans +[i])

def allcut(n):
b = []
for i in range(1,1+n):
b += list(naturalcut(n,i,1))
return b

# 上面两个函数和后面代码出现两个类似的函数完全是一致的,只是表现形式不一样
# 上面的简单明了,后面的效率更高一点,所以两个都保存了。

def getbn(n):
if n <= 1: return 1;
bn=[1]
for t in range(1,1+n):
bn.append(0)
for x in allcut(t):
product = 1
for i in x:
product *= bn[i-1]
bn[-1] += product
return bn

for i,x in enumerate(getbn(8)):
print(str(i)+'只相同猫咪有 '+ str(x)+'种状态')

我们现在考虑不同猫咪的情况

我们依然根据猫咪在场上的数量 $p_1 + \cdots +p_r$ ,对猫咪进行讨论,则有

真实包含了$x_i$ 只猫的猫有 $p_i$只 (这也是为什么$x_i$ 严格递增),

$x_i ^{p_i}$ :每只猫都要选择一个出来当最外面的猫

$a_{x_i - 1}^{p_i}$ : 去掉最外面的猫,里面有 $x_i -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
#正整数拆分 n = x_1p_1 + ... + x_rp_r, 且 low<=x_1<...<x_r
#low 表示递归的时候最小取值
#ans 保存递归得到的前部分
def naturalcuts(n, r, low, ans = []):
if r == 1:
for i in range(1,1+n//low):
if n%i == 0: yield ans + [(n//i,i)]
elif r >1:
x = n - r*(r-1)//2;
for i in range(low, 1 + x//r):
for j in range(1, x//i - r +2):
yield from naturalcuts(n-i*j,r-1,i+1,ans + [(i,j)])

def allcuts(n):
a = []
for i in range(1,1+n):
a += list(naturalcuts(n,i,1))
return a

import math
def getan(n):
an = [1];
for t in range(1,1+n):
an.append(0)
factn = math.factorial(t)
for item in allcuts(t):
product = factn
for x,p in item:
product //= math.factorial(x)**p
product //= math.factorial(p)
product *= an[x-1]**p
product *= x**p
an[-1] += product
return an

print(getan(10)) #9只不同猫咪状态数是 100000000(正好一亿)!!! 这也太整了吧

代码能如此简洁多亏了,Python的这个生成器写法太优美了!!!

当然了,如果只是5只猫咪,那我们其实也可以枚举出所有情况得到$a_n = 1296, b_n = 20$:

0

以下内容更新于 2020/3/17

在和我大学同学祺祺讨论之后,他猜测 $a_n = (n+1)^{n-1}$,一开始我是不相信的,不过数据对比之后发现,卧槽,秀啊。所以说明有一种更优美的理解:

假定LOL峡谷地图实际上在一只超大的$0$ 号猫咪肚子里面,那么这些猫咪就构成了以$0$为根的树,我们求得这$n+1$个(有编号)节点无根树个数,然后我们把$0$号节点变成根,就得到了我们所有的状态。

$n$ 个节点的无根树个数是$n^{n-2}$,最早于 A.Cayley 在 1889年首先公布并证明(现在看来不算严谨的证明),后来有了树的Prufer编码,就可以漂亮的解决证明这个问题了。可参考Matrix67的博客 或下面说明

Prufer 编码

$n$ 个节点的无根树(也就是简单无向图),可以唯一的给出一个长度为$n-2$ 的编码,同样每一个长为$n-2$ 的编码都可以唯一的产生一棵$n$个节点的无根树 (这就证明了上面结论)

给定一颗$n>2$个节点的无根树,每次找出无根树中,度数为$1$ 的节点中编号最小的节点$A$,记录节点$A$的邻接点,然后删除节点 $A$ 和它的边。这样一直继续下去,直到只剩下两个节点。

度数为$i$ 的节点恰好在 Prufer 编码中出现 $i-1$ 次

给你一个长度为$n-2$的Prufer编码,我们只要找出没有在当前编码中最小的跟编码中第一个节点相连即可。重复下去即可得到无根树。

后来我发现,我$b_n$ 算错了!!!,因为很多情况算重复了,为了算$b_n$

上述公式包括正整数拆分给相同的球染色问题

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
#正整数拆分 n = x_1p_1 + ... + x_rp_r, 且 low<=x_1<...<x_r
#low 表示递归的时候最小取值
#ans 保存递归得到的前部分
def naturalcuts(n, r, low, ans = []):
if r == 1:
for i in range(1,1+n//low):
if n%i == 0: yield ans + [(n//i,i)]
elif r >1:
x = n - r*(r-1)//2;
for i in range(low, 1 + x//r):
for j in range(1, x//i - r +2):
yield from naturalcuts(n-i*j,r-1,i+1,ans + [(i,j)])

def allcuts(n):
a = []
for i in range(1,1+n):
a += list(naturalcuts(n,i,1))
return a

import math

def getbn(n):
if n <= 1: return 1;
bn=[1]
for t in range(1,1+n):
bn.append(0)
for item in allcuts(t):
product = 1
for x,p in item:
product *= math.comb(bn[x-1]+p-1,p)
bn[-1] += product
return bn

print(getbn(10))

这正好是$n+1$ 个无编号的有根树个数

如有帮助,烦请资瓷(一块也是爱0.0)