How to generate all matrix multiplication order combinations : <p>I have searched quite extensively but couldn't find any solution</p>

<p>Any programming language answer is accepted. Especially C, Java, C# </p>

<p>I prefer C# though</p>

<p>So here my question</p>

<p>Example 1</p>

<p>Assume that I have the following matrices</p>

<pre><code>A1, A2, A3
</code></pre>

<p>So they can be multiplied as the following orders</p>

<pre><code>A1*A2*A3
A1*(A2*A3)
(A1*A2)*A3
</code></pre>

<p>Another example</p>

<pre><code>A1, A2, A3, A4, A5
</code></pre>

<p>Several of the possible multiplication orders are as below</p>

<pre><code>        (A1*A2)*(A3*A4)*A5

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

        A1*(A2*A3*A4*A5)
               .
               .
               .
</code></pre>

<p>So any ideas how to design an algorithm to find all?</p>

<p>It can be recursive, memory having dynamic?</p>
