Saturday, 29 September 2018

Possible Combination of Parentheses in a Matrix Chain Application

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.



from Possible Combination of Parentheses in a Matrix Chain Application

No comments:

Post a Comment