Hi and welcome to the Matladpi blog! In this post I will talk about the lexicographic order the tree generation algorithm is at least partially utilizing.
I think a good way to get a grasp of the order is to look at some examples, without the different possible forms a branch could have.
For example, the rooted tree sum form
1 + 1×7
would have the following forms in tree generation algorithm's lexicographic order, if we exclude the different forms a branch can have:
1 + 2 + 1×5
1 + 2×2 + 1×3
1 + 2×3 + 1
1 + 3 + 1×4
1 + 3 + 2 + 1×2
1 + 3 + 2×2
1 + 3×2 + 1
1 + 4 + 1×3
1 + 4 + 2 + 1
1 + 4 + 3
1 + 5 + 1×2
1 + 5 + 2
1 + 6 + 1
1 + 7
Now, if we look at the forms a branch can have, we see similar behaviour:
1 + 5
1 + (1 + 2 + 1×2)
1 + (1 + 2×2)
1 + (1 + 3 + 1)
1 + (1 + (1 + 2) + 1)
1 + (1 + 4)
1 + (1 + (1 + 2 + 1))
1 + (1 + (1 + 3))
1 + (1 + (1 + ( 1 + 2)))
Njäf! said.
I am Jesse Sakari Hyttinen and I will see you in the next post!