Re: Enumerating all expression trees (not Catalan)
- From: Tegiri Nenashi <tegirinenashi@xxxxxxxxx>
- Date: Wed, 16 Sep 2009 09:20:44 -0700 (PDT)
On Sep 15, 9:53 pm, Tegiri Nenashi <tegirinena...@xxxxxxxxx> wrote:
I'm writing a program that generates all expressions with binary and
unary operations. E.g. -((x + y) * z). Before worrying about
variables and operations, I wonder how to generate plain tree
structures. The mapping that would enumerate each tree with unique
integer would be ideal for my purposes. (Curiously, such mapping in
simple cases of binary trees or other Catalan structures is appeared
to be not an easy matter to google!)
Here is one such mapping. Assign 2 to a node with two children, 1 to
the node with one child, 0 to the leaf. Write down expression in
polish notation, and interpret it as a ternary number, e.g.
221000
corresponds to the tree or expression like this
(((-x)+y)+z)
However, this mapping is not a bijection, for example the code
22100
doesn't correspond to any tree. This might be a big problem for my
program if asymptotically the mapping is almost empty, then the run
time would be wasted wading through the list of mostly useless codes.
Any guess for asymptotic, or suggestion for better encoding?
Here is asymptotics:
10000 - 225
100000 - 1696
1000000 - 13695
10000000 - 108540
Admittedly, this should be done in base3 rather than 10 to give better
feeling of analytics. However my purpose was to establish if the
method is practical or not, and this experiment proved it does...
.
- References:
- Enumerating all expression trees (not Catalan)
- From: Tegiri Nenashi
- Enumerating all expression trees (not Catalan)
- Prev by Date: How to prove that a identity map is continous
- Next by Date: Re: Enumerating all expression trees (not Catalan)
- Previous by thread: Re: Enumerating all expression trees (not Catalan)
- Next by thread: diff eq. question
- Index(es):
Relevant Pages
|
Loading
