矩阵链应用程序中括号的可能组合

Question

我研究了矩阵链乘法，其中给定一个矩阵序列，目标是找到最有效的矩阵相乘方法。问题实际上不是执行乘法，而只是决定所涉及的矩阵乘法的顺序。这就是为什么我的任务是制作一个程序，该程序输出矩阵乘法中所有可能的矩阵组合，将 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 的范围内。我现在头很痛。请帮忙。

Answer 1

看起来您想将字符集划分为所有可能的子集，尽管您似乎没有考虑非连续分组（例如 (AC)(DB)）。如果是这样，这是一个众所周知的问题，存在众所周知的解决方案。