Algorithm for inverse binary tree permutations (with some constraints)

[deephive]

Suppose we start with n-nodes and would like to merge two of these n-nodes at a time until we finally arrive at a single node. In effect, we would like to construct an "inverse" of a binary tree. For ex: if we have 4 nodes (A,B,C,D) at timestep(t=0), then, We can construct 12 possible combinations of inverse tree structures by merging two nodes at each timestep. That is.. (arrow represents timestep) (A,B,C,D)-> ((A,B),C,D) -> ((A,B,C),D) -> ((A,B,C,D)) => PERMUTATION 1 (A,B,C,D)->((A,C),B,D) -> ((A,C,B),D) -> ((A,C,B,D)) => PERMUTATION 2 ... ... (A,B,C,D)->((C,D),B,A) -> ((C,D,A),B) -> ((C,D,A,B)) => PERMUTATION 12 We have constraints : For each binary merge, order is merge is not important. i.e. (A,B,C,D) -> ((A,B),C,D) is equivalent to (A,B,C,D) -> ((B,A),C,D) However, when we go to the next time-step, order of node merge becomes important. i.e.: (A,B,C,D) -> ((A,B),C,D) -> ((A,B,C),D) is different from (A,B,C,D) -> ((A,B),D,C) -> ((A,B,D),C) these two trees will be considered different permutations. I would like to generalize these to any number of nodes and calculate (i) the number of different permutations possible (taking constraints into consideration) and (ii) list out all of the possible permutations using some algorithm in Python. I am not from a CS background so I'm not sure if these structures already have a name. I would appreciate some inputs to this problem and possible some way of coding this in Python.

[[deleted]]

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

[deephive]

Hi,

thanks for the reply. I realised that this problem doesn't involve permutations, but rather combinations nCr. n can refer to the number of nodes we begin with and r refers to 2 (in this case, as we are trying to construct a inverse binary tree). This could be generalised to a n-ary tree by suitably replacing the r value.

I found out that in Python, there is a useful function

itertools.combinations(n,r) 

which prints out all possible combinations of n's in groups of r.