Algorithm for the complete parenthesization of n factors 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.
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.