Possible Combination of Parentheses in a Matrix Chain Application

Question

I have studied matrix chain multiplication, wherein given a sequence of matrices, the goal is to find the most efficient way to multiply matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved. That is the reason why I am tasked to make a program that outputs all possible combinations of matrices in a matrix multiplication given n as the number of matrices as an input. For example

 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)

My intial code was below, called by

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

The output of the code above when my inout is 4 matrices is:

(AB)(CD)
A(BC)D
(AB)(CD)
(ABC)D
A(BCD)

How can I revise my code. The number of matrices must be in the range 1-26. My head now is aching. Please help.

Answer 1

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_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

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)F
39 (((AB)(CD))E)F
40 (((A(BC))D)E)F
41 ((((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)
>>> 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)')

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

Answer 2

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.

Answer 3

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