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

This is related to the Catalan number. It, however, merely determines the number of such occurrences, while keeping a given factor order.

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.

Additionally, if the factors are commutative (thus not matrices in the general case), the number of combinations is larger than the Catalan number. As an example, given the above input, additional elements in the output are expected { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))", "(ac)(bd)", "d(b(ca))", ... }. In other words, if the factors are commutative, the matrix chain multiplication problem and Catalan number considerations are no longer applicable (at least I can't make a fruitful connection).

So, the question focuses primarily on the algorithm for the general case, i.e. when commutative factors are involved.

  • $\begingroup$ Look for "Matrix-Chain Multiplication" - there are many explanations on net how to do that $\endgroup$
    – HEKTO
    Aug 12 '19 at 14:00
  • $\begingroup$ @HEKTO I did, the problem is that the matrix multiplication is not commutative, which is not true in the general case. There are more combinations than the Catalan number. This is why I started from that problem, but have yet to find a solution for the general case. $\endgroup$ Aug 19 '19 at 13:06
  • $\begingroup$ There are more combinations than the Catalan number - it's unclear why. Can you please state that more clearly in your question? $\endgroup$
    – HEKTO
    Aug 19 '19 at 13:36
  • $\begingroup$ @HEKTO I agree that the clarification was needed, so I added details to provide more focus to the question. I must also admit, that my problem became easier to describe after additional research. But. although my understanding has improved, I'm still not closer to a solution. $\endgroup$ Aug 20 '19 at 6:46
  • $\begingroup$ So basically you want an algorithm to generate all leaf-labelled trees over $n$ leaf elements? Are "(ab)(cd)" and "(cd)(ab)" considered equivalent, and only one of them should be generated, or is the order of left and right edges significant? $\endgroup$ Aug 20 '19 at 11:09

As with most things involving trees, it's easiest to analyse recursively.

Given a one-element set $\{a\}$, the only parenthesisation is $(a)$.

Given a larger set $S$, we choose an arbitrary element $x \in S$. Then for each proper subset $T \subset (S \setminus \{x\}) $ we have parenthesisations $(p)(q)$ where $p$ is a parenthesisation of $\{x\} \cup T$ and $q$ is a parenthesisation of the remaining elements. There are a total of $(2|S| - 3)!!$ such.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.