Вот рекурсивная схема, которая работает задом наперед.
Она реализована в виде генератора part, который начинается с умножения last .Это последнее умножение должно быть между двумя факторами, левый из которых является произведением по первым j (переменная cut в коде ниже) матриц («левый блок») и правым из которых является произведениеповерх оставшихся матриц («правый блок»). j может быть любым значением от 1 до N -1, где N - количество матриц в цепочке.
Поэтому для перечисления всехгруппировки мы должны перебрать j .Для каждого j мы должны объединить каждую группировку левого блока с каждой группировкой правого блока.Для перечисления группировок блоков мы используем 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