# Algorithm for the complete parenthesization of n factors

Is there an algorithm that can list all possible parenthesizations of a given set of factors?

This is related to the Catalan's number. It, however, merely determines the number of such occurrences.

As an example (found at the above link): from "abcd", the algorithm should produce { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))" }.

Another related problem is the optimal matrix multiplication order, where given a number of matrices that ought to be multiplied together, the task is to parenthesize them in an order such as the resulting multiplication operations take the least computational resources. From this, I tried to work out an exhaustive way to list all possibilities, but wasn't able to.

• Look for "Matrix-Chain Multiplication" - there are many explanations on net how to do that – HEKTO Aug 12 at 14:00