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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.