How to generate all matrix multiplication order combinations

Question

I have searched quite extensively but couldn't find any solution

Any programming language answer is accepted. Especially C, Java, C#

I prefer C# though

So here my question

Example 1

Assume that I have the following matrices

A1, A2, A3

So they can be multiplied as the following orders

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

Another example

A1, A2, A3, A4, A5

Several of the possible multiplication orders are as below

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

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

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

So any ideas how to design an algorithm to find all?

It can be recursive, memory having dynamic?

Answer 1

In order to have all the combination, I used the array "group" in order to retain which matrix are in which parenthesis. For instance, a group of 1 is "(M)", a group of 2 is "(M * M)", a group of 3 is "(M * M * M)", etc etc

So, if we have 5 matrice, then

• group = [1, 1, 1, 1, 1] give "(M) * (M) * (M) * (M) * (M)".
• group = [4, 0, 0, 0, 1] give "(M * M * M * M) * (M)"

I used value in "group" like that : If it's a number > 0, then it the number of matrice held in the group. If it's 0, the matrice are "owned" by the first value != 0 with a lesser indice.

Exemple : group = [2, 0, 3, 0, 0]

The 0 in indice 1 mean that the matrice in indice 1 is "owned" by the group in indice 0. The 0 in indice 4 mean that the matrice in indice 4 is "owned" by the group in indice 2 (and not 0).

You can now use "group" to know how to calculate your actual matrice (mine is just a string).

Now, the core of the algorithm just lie in how can I have the next "group". For that, I use the following rules (I iterate througth the array from the end to the start) :

• find the second group and increment his size

Why the second group ? Because you can never increment the first one without having too much matrices in the end.

If group = [1, 1, 1, 1, 1], there are 5 matrices. If I increment the first group, then [1, 1, 1, 1, 2] will have 6 matrices, which is impossible.

• Set to 0 all the following matrices that are in the newly incremented group.

• And then, set all the following matrice to group of 1

Here is a new code, can you understand it ?

#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);
}

---

---

old code (recursion useless, matrice array useless, and finding next group algorithm more complexe).

#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)
    */

}