Generate random labeled tree with constrained edge lengths

Question

Let $T$ be a labeled tree with vertices $V = \{1, \dots, n\}$ and edges $E$. Define the length of an edge $e = \{ u, v \}, u \in V, v \in V$ to be $l(e) = |u - v|$, i.e. the distance between the nodes in the linear arrangement of the tree. Let the length sequence $L$ of $T$ be the sorted sequence of lengths of all the edges in $T$.

An example tree is shown below. Each edge is marked with its length. The length sequence for this tree is $(1, 1, 1, 1, 2, 2, 3)$.

My question is: Given a length sequence $L$, is there an efficient algorithm to generate a labeled tree $T$ with length sequence $L$, randomly at uniform from the set of all such trees? Or failing that, to enumerate the set of trees with a given length sequence $L$?

To clarify, here is an extremely inefficient algorithm that does what I want. We have a desired length sequence $L$, let's say (1,1,1,1,2,2,3). To generate a random tree with the desired edge lengths:

1. Generate a random labeled tree $T$ on $n=8$ nodes by sampling a random Prüfer code.
2. Check if the length sequence of $T$ matches $L=(1,1,1,1,2,2,3)$. If yes, accept $T$. If not, goto 1.

This is very inefficient because there are $n^{n-2}$ possible trees generated in step 1, and only a very small number of those trees matches the desired $L$, especially as the trees get large.

Update: I have an algorithm that seems to work, but it seems like it could be made more efficient.

Algorithm:

1. Let $T$ be a graph with nodes $V$ and empty edge set $E$.

2. For each possible edge length $l$ in $\{1, \dots, \text{max}(L)\}$,

3. Let $k$ be the number of entries in $L$ matching $l$. So for example, if $L=(1,1,1,1,2,2,3)$ and $l=1$, then $k=4$.

4. If $k=0$, skip to the next $l$.

5. Generate the set of possible new edges $P = \{(u,v) : u \in V, v \in V, (u,v) \not\in E, u = v+l \text{ or } u = v-l\}$

6. If $P$ is empty, fail and start over again from 1.

7. Generate the set $Q$ of all combinations of size $k$ of elements of $P$

8. Randomly choose an element of $Q$, which is a set of $k$ edges. Add this set of edges to $E$.

9. If the resulting $T$ is not a forest, fail and start over again from 1. Otherwise, continue to the next $l$.

Basically, this generates the random graphs matching $L$, then filters them to be trees.

Answer 1

I'm not entirely sure of what you're asking for, but I think it might be one of these three:

Permutations that preserve topological structure
The tree you listed in parenthetical notation is (5 (2 (1 4) ) (3) (5 (6 (7 (8) ) ) ). Are you looking for permutations of this tree structure, because you can simply calculate all n! permutations of nodes and put them in the same tree structure:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (5) (4 (3 (1 (2) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (2 (3) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (3 (2) ) ) )
...
(This would yield 362,880 distinct trees).

Note, this class of trees would preserve the sequences of lengths of the current tree. Now, if you have an array of these, simply use a good PRNG.

Permutations that calculate topological isomorphisms
It also would preserve topological properties, so if you want to generate other isomorphic topologies, then you can take the structure of the tree and do permutations on the sequences at the same level. Hence:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (4 (3 (2 (1) ) ) (5) )
(9 (5) (8 (7 6) ) (4 (3 (2 (1) ) ) )
(9 (5) (4 (3 (2 (1) ) ) (8 (7 6) ) )
...
(This will be a variable number of permutations, in this case (3!(1!)(2!)(1!)) or 12 trees.)

Permutations that calculate equivalent lengths

Let your tree be [1 2[1 4] 3 4 *5[2 3 6] 6[7] 7[8] 8] where * represents root, and nodes inside of brackets are pointers. Notice it's possible to calculate lengths by taking the absolute value of the difference between nodes (2[4]->2[[2]] The node two which points to [node four] is a node that has an [[edge length 2]]). Then use [1 2[[1 2]] 3 4 *5[[3 2 1]] 6[[1]] 7[[1]] 8 9] -> {1, 1, 1, 1, 2, 3}. Now we can simply replicate this by traversing the original tree and constructing isomorphisms of length. Hence:

1. Determine root
   Rnd(1-9)->3 -> [1 2 *3 4 5 6 7 8]
2. Permute first level by taking three lengths and finding candidates
   [1 2 *3[[3 2 1]] 4 5 6 7 8 9]-> (note three lengths)
   [3]±[[3]]->{0,6} (0 is invalid so don't push on the stack)
   [3]±[[2]]->{1,5}
   [3]±[[1]]->{2,4}
   Note we need to select P(2,1) on all three sets iteratively.
   So, randomly, one permutation is {6,1,4} :[1[] 2 *3[1 4 6] 4[] 5 6[] 7 8].
3. Call this recursively on [1], [4], [6] over the set {with [[1], [[1]], and [[1 2]] with the base case being any tree that satisfies {1, 1, 1, 1, 2, 3}.

Now, I think that preserving the lengths as a function of order of the sequence might yield a very small set, because certain trees, might only have a single isomorphism. Consider:

(1 (2 (3 (4 (5 (6 (7 (8)))))))) ~ (8 (7 (6 (5 (4 (3 (2 (1))))))))
{1 1 1 1 1 1 1} = {1 1 1 1 1 1 1}

There's only one isomophism because of the way a tree when considering edges whose lengths are caculated from sequences partitions. In fact, every tree done in this manner might have at most 1, but I'd have to think about how to prove that after implementing code.

Let me know what you think; if you can clarify what you're seeking, I might be able to help.