java - 如何生成所有矩阵乘法顺序组合

Question

我进行了广泛的搜索，但找不到任何解决方案

接受任何编程语言的答案。特别是 C、Java、C#

不过我更喜欢 C#

这是我的问题

示例1

假设我有以下矩阵

A1, A2, A3

所以它们可以按以下顺序相乘

A1*A2*A3
A1*(A2*A3)
(A1*A2)*A3

另一个例子

A1, A2, A3, A4, A5

几种可能的乘法顺序如下

        (A1*A2)*(A3*A4)*A5

        A1*(A2*A3)*(A4*A5)

        A1*(A2*A3*A4*A5)
               .
               .
               .

那么有什么想法可以设计一个算法来查找所有内容吗？

可以递归，内存具有动态性？

Answer 1

为了获得所有组合，我使用了数组“group”来保留哪个矩阵位于哪个括号中。 例如，1 组为“(M)”，2 组为“(M * M)”，3 组为“(M * M * M)”，等等

所以，如果我们有 5 个矩阵，那么

• group = [1, 1, 1, 1, 1] 给出“(M) * (M) * (M) * (M) * (M)”。
• group = [4, 0, 0, 0, 1] 给出“(M * M * M * M) * (M)”

我在“组”中使用了这样的值: 如果它是一个> 0的数字，那么它是组中保存的矩阵的数量。 如果为 0，则矩阵由第一个值“拥有”!= 0 且索引较小。

示例:组 = [2, 0, 3, 0, 0]

索引 1 中的 0 表示索引 1 中的矩阵由索引 0 中的组“拥有”。 索引 4 中的 0 表示索引 4 中的矩阵由索引 2 中的组“拥有”(而不是 0)。

您现在可以使用“group”来了解如何计算实际矩阵(我的矩阵只是一个字符串)。

现在，算法的核心在于如何拥有下一个“组”。 为此，我使用以下规则(我从末尾到开头迭代数组):

• 找到第二组并增加其大小

为什么是第二组？因为如果最后没有太多矩阵，你永远无法增加第一个矩阵。

如果 group = [1, 1, 1, 1, 1]，则有 5 个矩阵。 如果我增加第一组，那么 [1, 1, 1, 1, 2] 将有 6 个矩阵，这是不可能的。

• 将新增加的组中的所有以下矩阵设置为 0。

• 然后，将以下矩阵全部设为1组

这是一段新代码，你能理解吗？

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

#define NB_MAT 3

void MatriceGroupDisplay(int group[NB_MAT])
{
    for (int i = 0; i < NB_MAT; ++i) {
        if (group[i] > 1) {
            printf("(");
        }
        printf("M%d", i + 1);
        if (group[i] == 0 && (i + 1 >= NB_MAT || group[i + 1] != 0)) {
            printf(")");
        }
        if (i != NB_MAT - 1) {
            printf(" * ");
        }
    }
    printf("\n");
}

bool FoundNextMatriceGroup(int group[NB_MAT])
{
    int i;
    int nbGroup = 0;

    // There are one group, so no more combination is possible
    if (group[0] == NB_MAT) {
        return (false);
    }
    // We found the second group ...
    for (i = NB_MAT - 1; nbGroup != 2; --i) {
        if (group[i] != 0) {
            ++nbGroup;
        }
    }
    ++i;
    // ... and increment it's size.
    ++group[i];
    // All the following "matrix" are in the group ...
    for (int j = 1; j < group[i]; ++j) {
        group[i + j] = 0;
    }
    // ... and all the following group have a size of 1
    for (int j = i + group[i]; j < NB_MAT; ++j) {
        group[j] = 1;
    }

    return (true);
}

int main(void)
{
    int group[NB_MAT];

    for (size_t i = 0; i < NB_MAT; ++i) {
        group[i] = 1;
    }

    MatriceGroupDisplay(group);
    while (FoundNextMatriceGroup(group)) {
        MatriceGroupDisplay(group);
    }
    return (EXIT_SUCCESS);
}

<小时/> <小时/>

旧代码(递归没用，矩阵数组没用，查找下一组算法更复杂)。

#include <stdio.h>

#define NB_MAT 5

void matDisplay(char *matrices[NB_MAT], int group[NB_MAT])
{
    for (int i = 0; i < NB_MAT; ++i) {
        if (group[i] > 1) {
            printf("(");
        }
        printf("%s", matrices[i]);

        if (group[i] == 0 && (i + 1 >= NB_MAT || group[i + 1] != 0)) {
            printf(")");
        }
        if (i != NB_MAT - 1) {
            printf(" * ");
        }

    }

    printf("\n");
}

void rec(char *matrices[NB_MAT], int group[NB_MAT])
{
    matDisplay(matrices, group);

    int i = NB_MAT - 1;

    // We found the first "group" that we can increase in size
    while (i >= 0) {
        if (group[i] != 0 && group[i] + 1 <= NB_MAT - i) {
            ++group[i];
            break;
        }
        --i;
    }
    if (i < 0) {
        return ;
    }

    // The following matrice are in the "group"
    int nbInGroup = group[i];
    for (int j = 1; j < nbInGroup; ++j) {
        group[i + j] = 0;
    }

    // All the other group is 1
    for (int j = i + nbInGroup; j < NB_MAT; ++j) {
        group[j] = 1;
    }

    rec(matrices, group);
}

int main(void)
{
    char *matrices[NB_MAT] = {"M1", "M2", "M3", "M4", "M5"};
    int  group[NB_MAT]     = {1, 1, 1, 1, 1};

    rec(matrices, group);

    /*
    11111 (a)*(b)*(c)*(d)*(e)
    1112. (a)*(b)*(c)*(d*e)
    112.1 (a)*(b)*(c*d)*(e)
    113.. (a)*(b)*(c*d*e)
    12.11 (a)*(b*c)*(d)*(e)
    12.2. (a)*(b*c)*(d*e)
    13..1 (a)*(b*c*d)*(e)
    14... (a)*(b*c*d*e)
    2.111 (a*b)*(c)*(d)*(e)
    2.12. (a*b)*(c)*(d*e)
    2.2.1 (a*b)*(c*d)*(e)
    2.3.. (a*b)*(c*d*e)
    3..11 (a*b*c)*(d)*(e)
    3..2. (a*b*c)*(d*e)
    4...1 (a*b*c*d)*(e)
    5.... (a*b*c*d*e)
    */

}