我研究了矩阵链乘法,其中给定一个矩阵序列,目标是找到最有效的矩阵相乘方法。问题实际上不是执行乘法,而只是决定所涉及的矩阵乘法的顺序。这就是为什么我的任务是制作一个程序,输出矩阵乘法中所有可能的矩阵组合,给定 n 作为输入的矩阵数。例如
n == 1 (A)
n == 2 (AB)
n == 3 (AB)C , A(BC)
n== 4 ((AB)C)D, (A(BC))D, A((BC)D), A(B(CD)), (AB)(CD)
我的初始代码如下,由
调用 possible_groupings(4) #4 matrices
def possible_groupings(n):
print("Possible Groupings : ")
total = 0
if(n==1):
print('A')
total = total + 1
elif(n==2):
print('(AB)')
total = total + 1
else:
a = 2
while(a <= n-1):
b = 0
while((b+a) <= (n )):
c = b
d = 0
substr = ''
while (d < c):
substr = substr + chr(65 + d)
d = d + 1
if substr != '':
if len(substr) == 1:
print( substr, end = '')
else:
print('(' + substr + ')', end = '')
print('(', end = '')
while (c < (b +a)):
print(chr(65 + c), end = '');
c = c + 1
print(')', end = '')
e = b+a
substr = ''
while (e < n):
substr = substr + chr(65 + e)
e = e + 1
if substr != '':
if len(substr) == 1:
print( substr, end = '')
else:
print('(' + substr + ')', end = '')
print('')
total = total + 1
b = b + 1
a = a + 1
print('Total : ' + str(total))
当我的 inout 是 4 个矩阵时,上面代码的输出是:
(AB)(CD)
A(BC)D
(AB)(CD)
(ABC)D
A(BCD)
如何修改我的代码。矩阵的数量必须在 1-26 范围内。我现在头很痛。请帮忙。
最佳答案
这是一个从后到前工作的递归方案。
它被实现为一个生成器,部分
,以最后 乘法开始。最后的乘法必须在两个因子之间进行,这两个因子的左边是第一个 j(下面代码中的变量 cut
)矩阵(“left block”)和右边是剩余矩阵的乘积(“右边 block ”)。 j 可以是 1 到 N-1 之间的任何值,其中 N 是链中矩阵的数量。
因此,要枚举所有分组,我们必须遍历 j。对于每个 j,我们必须将左侧 block 的每个分组与右侧 block 的每个分组组合起来。为了枚举 block 的分组,我们使用 part
本身,即递归。
def part(names, top=True):
lr = ('', '') if top else '()'
if len(names) <= 1:
yield names
elif len(names)==2:
yield names.join(lr)
else:
for cut in range(1, len(names)):
for left in part(names[:cut], False):
for right in part(names[cut:], False):
yield (left+right).join(lr)
最小化器可以使用相同的逻辑。这可以利用 functools.lru_cache
提供的内存:
from functools import lru_cache
from string import ascii_uppercase
@lru_cache(None)
def _min_no_mult(dims):
if len(dims) == 2:
return 0, 'x'
elif len(dims)==3:
return dims[0]*dims[1]*dims[2], 'xx'.join('()')
cuts = ((cut, *_min_no_mult(dims[:cut+1]), *_min_no_mult(dims[cut:]))
for cut in range(1, len(dims)-1))
return min((mnl + mnr + dims[0]*dims[-1]*dims[cut], (nml+nmr).join('()'))
for cut, mnl, nml, mnr, nmr in cuts)
def min_no_mult(dims, names=None):
mn, argmn = _min_no_mult(tuple(dims))
names = iter(ascii_uppercase if names is None else names)
argmn = argmn[1:-1] if len(dims) > 2 else argmn
argmn = ''.join(next(names) if a=='x' else a for a in argmn)
return mn, argmn
演示:
>>> for i, j in enumerate(part(ascii_uppercase[:6])):
... print(i, j)
...
0 A(B(C(D(EF))))
1 A(B(C((DE)F)))
2 A(B((CD)(EF)))
3 A(B((C(DE))F))
4 A(B(((CD)E)F))
...
38 ((A((BC)D))E)F
39 (((AB)(CD))E)F
40 (((A(BC))D)E)F
41 ((((AB)C)D)E)F
由于内存,最小化器可以轻松处理大量维度:
>>> import numpy as np
>>> dims = np.clip(np.arange(-1, 26), 1, None)
>>> np.random.shuffle(dims)
>>> dims
array([ 5, 25, 1, 4, 14, 24, 7, 15, 2, 12, 11, 9, 18, 8, 19, 13, 23,
17, 1, 22, 21, 1, 16, 6, 3, 20, 10])
>>> min_no_mult(dims)
(3383, '(AB)((((((((((CD)E)F)G)H)(I(J(K(L(M(N(O(P(QR))))))))))((ST)U))((VW)X))Y)Z)')
我们可以查询一些基本的缓存统计数据:
>>> _min_no_mult.cache_info()
CacheInfo(hits=5450, misses=351, maxsize=None, currsize=351)
这可能看起来不起眼,但请记住,每次命中都会剪切整个子树。
的确,我们可以再次循环使用递归方案并计算括号的数量:
@lru_cache(None)
def count(n):
if n <= 2:
return 1
else:
return sum(count(cut) * count(n-cut) for cut in range(1, n))
对于 26 个矩阵,有很多方法可以将它们括起来:
>>> print(f"{count(26):,d}")
4,861,946,401,452
关于python - 矩阵链应用中括号的可能组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52529409/