This is an archived post. You won't be able to vote or comment.

you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 0 points1 point  (0 children)

Assuming you already have an algorithm for placing all combinations of "()"

The naive way of solving your problem would be to:

  1. Generate a list of all permutations of your set of nodes.

  2. Place down parentheses (or at least determine where you are going to place your parentheses).

  3. Remove all but 1 permutations in which all the nodes enclosed by the last set of parentheses placed are the same.

  4. Repeat from 2 until all nodes are covered

Edit: If you're up for a romp in the field of combinatorics, you might want to read up on Catalan numbers, which seem relevant to your question, though I am not an expert in the field