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

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 个矩阵，那么

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

我在 "group" 中使用了这样的值：如果它是 > 0 的数字，则它是组中包含的矩阵数。如果它是 0，则矩阵 "owned" 乘以第一个值 != 0 和较小的索引。

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

索引1中的0表示索引1中的矩阵被索引0中的组"owned"。索引 4 中的 0 表示索引 4 中的矩阵被索引 2 中的组 "owned"（而不是 0）。

您现在可以使用 "group" 了解如何计算您的实际矩阵（我的只是一个字符串）。

现在，算法的核心就在于how can I have the next "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)
    */

}

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

How to generate all matrix multiplication order combinations

c

c#

java

algorithm

matrix-multiplication