Possible Combination of Parentheses in a Matrix Chain Application

Here is a recursive scheme that works back-to-front.

It is implemented as a generator, part, that starts with the last multiplication. This last multiplication must be between two factors the left of which is a product over the first j (variable cut in the code below) matrices ("left block") and the right of which is a product over the remaining matrices ("right block"). j can be anything between 1 and N-1 where N is the number of matrices in the chain.

Therefore, to enumerate all groupings we must loop over j. For each j we must combine each grouping of the left block with each grouping of the right block. To enumerate the groupings of the blocks we use part itself, i.e. recursion.

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)

The same logic can be used for the minimizer. This can utilize memoization as provided by functools.lru_cache:

from functools import lru_cachefrom 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

Demo:

>>> 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)F39 (((AB)(CD))E)F40 (((A(BC))D)E)F41 ((((AB)C)D)E)F

Thanks to memoization, the minimizer can easily handle large numbers of dimensions:

>>> import numpy as np>>> dims = np.clip(np.arange(-1, 26), 1, None)>>> np.random.shuffle(dims)>>> dimsarray([ 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)')

We can query some basic cache statistics:

>>> _min_no_mult.cache_info()CacheInfo(hits=5450, misses=351, maxsize=None, currsize=351)

This may look unimpressive but keep in mind that each hit cuts an entire subtree.

Indeed, we can once more recycle the recurrence scheme and count the number of bracketings:

@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))

For 26 matrices there are quite a few ways of parenthesizing them:

>>> print(f"{count(26):,d}")4,861,946,401,452

It looks like you want to partition the set of characters into all possible subsets, although you do not seem to have taken non-contiguous groupings (such as (AC)(DB)) into account. If so, it is a well-known problem for which well-known solutions exist. See for example How to find all partitions of a set.

There are Catalan(nmatrices-1) combinations, and we can use simple balanced parentheses algorithm to generate pre-combinations. Here is code to get both parentheses (for comparison) and matrix pre-combinations.

But I have not found concise method to set closing parentheses yet (cx argument is my attempt to count multiplications and deduce number of closing parens in given point).

Perhaps somebody might see simple formula/law to get the final result.

def genparens(s, maxlen, l, r):    if l + r == maxlen * 2:        print(s)        return    if l < maxlen:        genparens(s + '(', maxlen, l + 1, r)    if r < l:        genparens(s + ')', maxlen, l, r + 1)alpha = "ABCDEFGHIJK"def genmatparens(s, n, l, r, ci, cx):    if l + r == n * 2:        s = s + alpha[ci] # + ")" * cx        print(s)        return    if l < n:        genmatparens(s + '(', n, l + 1, r, ci, cx + 1)    if r < l:        s += alpha[ci]        #s += ")" * cx        s += "x"        genmatparens(s, n, l, r + 1, ci + 1, 1)genparens("", 3, 0, 0)print()genmatparens("", 3, 0, 0, 0, 0)((()))(()())(())()()(())()()()current           should be(((AxBxCxD        (((AxB)xC)xD)((Ax(BxCxD        ((Ax(BxC))xD)((AxBx(CxD        ((AxB)x(CxD))(Ax((BxCxD        (Ax((BxC)xD))(Ax(Bx(CxD        (Ax(Bx(CxD)))