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

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 matricesdef 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 + 1print('Total : ' + str(total))当我的 inout 是 4 个矩阵时，上面代码的输出是：(AB)(CD)A(BC)D(AB)(CD)(ABC)DA(BCD)我怎样才能修改我的代码。矩阵的数量必须在 1-26 的范围内。我现在头很痛。请帮忙。

Answer 1

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