I'm not familiar with this length sequence notationentirely sure of what you're asking for, so bear with me. It doesn't seem to preserve the nodesbut I think it might be one of the vertices.these three:
ThePermutations 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).
ItPermutations 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.)
If I didn't answerPermutations that calculate equivalent lengths
Let your questiontree be [1 2[1 4] 3 4 *5[2 3 6] 6[7] 7[8] 8] where * represents root, give me some feedback inand nodes inside of brackets are pointers. Notice it's possible to calculate lengths by taking the comments belowabsolute 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, and1, 1, 1, 2, 3}. Now we shouldcan simply replicate this by traversing the original tree and constructing isomorphisms of length. Hence:
- Determine root
Rnd(1-9)->3 -> [1 2 *3 4 5 6 7 8]
- 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].
- 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))))))))
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 get you therehelp.
