Currently I can enumerate rooted planar unlabeled binary trees using the following brute-force Prolog code.
e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].
Note: See output listings below.
and output them in increasing size using
es(S) :-
length(Ls, _),
phrase(e, Ls), % or e(Ls,[]),
atomic_list_concat(Ls,S).
However this is inefficient brute-force algorithm.
Is there a more efficient algorithm for enumerating rooted planar unlabeled binary trees?
Note: The trees can be generated by using the trees from the previous two iterations, think Fibonacci numbers, and adding either a unary branch or a binary branch, however this leads to duplicate trees. I myself could do that version, what I am looking for is an algorithm that generates the trees in an efficient manner the first time without duplicates.
Note: A binary tree is also known as a binary expression tree or a K-ary tree with K <=2.
Supplement
Results
My brute-force version for M(15) took 1 hr and 27 minutes,
while the efficient version for M(15) took about 2 seconds.
Obviously the efficient algorithm is just that, much more efficient and why I asked the question.
Motzkin numbers
The number of trees that have N nodes for a rooted planar unlabeled binary trees is given by Motzkin numbers. See: OEIS A001006
Nodes Trees
1 1
2 1
3 2
4 4
5 9
The number of trees that have N internal nodes for a rooted planar unlabeled binary tree is given by Catalan numbers. There is a more efficient algorithm for generating rooted planar binary trees using Catalan numbers.
Note:
The number of trees based on Catalan numbers do not have unary branches and count only internal nodes.
while
the number of trees based on Motzkin numbers do have unary branches and count all nodes.
See:
OEIS A000108
Catalan Numbers by Tom Davis
Relating Prolog list elements to Motzkin number
% M is Motzkin number, N is number of list elements passed to atomic_list_concat2
m_to_n(1,1).
m_to_n(2,3).
m_to_n(M,N) :-
M > 2,
N is (M*2)-1.
es_m(M,S) :-
m_to_n(M,N),
length(Ls,N),
e(Ls,[]),
atomic_list_concat(Ls,S).
Stats with inefficient brute-force version
es_c(M,Count) :-
aggregate_all(count, es_m(M,_), Count).
?- time(es_c(1,Count)).
% 57 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.
?- time(es_c(2,Count)).
% 141 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 1.
?- time(es_c(3,Count)).
% 571 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 2.
?- time(es_c(4,Count)).
% 2,740 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
Count = 4.
?- time(es_c(5,Count)).
% 13,780 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
Count = 9.
?- time(es_c(6,Count)).
% 70,072 inferences, 0.000 CPU in 0.002 seconds (0% CPU, Infinite Lips)
Count = 21.
?- time(es_c(7,Count)).
% 357,358 inferences, 0.016 CPU in 0.012 seconds (136% CPU, 22870912 Lips)
Count = 51.
?- time(es_c(8,Count)).
% 1,824,082 inferences, 0.063 CPU in 0.056 seconds (111% CPU, 29185312 Lips)
Count = 127.
?- time(es_c(9,Count)).
% 9,313,720 inferences, 0.297 CPU in 0.290 seconds (102% CPU, 31372531 Lips)
Count = 323.
?- time(es_c(10,Count)).
% 47,561,878 inferences, 1.469 CPU in 1.467 seconds (100% CPU, 32382555 Lips)
Count = 835.
?- time(es_c(11,Count)).
% 242,896,160 inferences, 7.672 CPU in 7.665 seconds (100% CPU, 31660599 Lips)
Count = 2188.
?- time(es_c(12,Count)).
% 1,240,493,974 inferences, 38.797 CPU in 38.841 seconds (100% CPU, 31974069 Lips)
Count = 5798.
?- time(es_c(13,Count)).
% 6,335,410,822 inferences, 206.047 CPU in 213.116 seconds (97% CPU, 30747425 Lips)
Count = 15511.
?- time(es_c(14,Count)).
% 32,356,235,848 inferences, 1016.156 CPU in 1018.955 seconds (100% CPU, 31841792 Lips)
Count = 41835.
?- time(es_c(15,Count)).
% 165,250,501,417 inferences, 5231.766 CPU in 5268.363 seconds (99% CPU, 31585991 Lips)
Count = 113634.
References
A free downloadable book as a pdf that might help is "Analytic Combinatorics" by Philippe Flajolet and Robert Sedgewick
Also see the references in the Catalan tag.
Motzkin numbers
BNF
<expression> ::=
<unary expression>
| <binary expression>
| <terminal>
<unary expression> ::=
"(u" <expression> ")"
<binary expression> ::=
"(b" <expression> " " <expression> ")"
<terminal> ::=
"t"
Using answer by David Eisenstat
Think of these as notes, or breadcrumbs, for me in case I need to use this again in many months after I forget it.
To test the answer I used WSL (Windows Subsystem for Linux) with Python 3 installed
Using Windows 10 I created a file named motzkin.py in the directory
C:UsersEricDocumentsProlog
with the Python code
def ubtrees(n):
if n == 1:
yield 't'
elif n > 1:
for t in ubtrees(n - 1):
yield '(u {})'.format(t)
for i in range(1, n - 1):
for t1 in ubtrees(i):
for t2 in ubtrees(n - 1 - i):
yield '(b {} {})'.format(t1, t2)
then in WSL I created a symbolic link to the Windows Prolog directory
$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog
and changed to the WSL Prolog directory
$ cd Prolog
then started Python3
~/Prolog$ python3
and imported the Python code
>>> import motzkin
and ran the following with the argument to ubtrees being the Motzkin number
>>> for value in ubtrees(1):
... print(value)
...
t
>>> for value in ubtrees(2):
... print(value)
...
(u t)
>>> for value in ubtrees(3):
... print(value)
...
(u (u t))
(b t t)
>>> for value in ubtrees(4):
... print(value)
...
(u (u (u t)))
(u (b t t))
(b t (u t))
(b (u t) t)
>>> for value in ubtrees(5):
... print(value)
...
(u (u (u (u t))))
(u (u (b t t)))
(u (b t (u t)))
(u (b (u t) t))
(b t (u (u t)))
(b t (b t t))
(b (u t) (u t))
(b (u (u t)) t)
(b (b t t) t)
and to check the Motzkin numbers
def m_count(m):
count = sum(1 for x in ubtrees(m))
print("Count: ", count)
>>> m_count(1)
Count: 1
>>> m_count(2)
Count: 1
>>> m_count(3)
Count: 2
>>> m_count(4)
Count: 4
>>> m_count(5)
Count: 9
>>> m_count(6)
Count: 21
>>> m_count(7)
Count: 51
>>> m_count(8)
Count: 127
>>> m_count(9)
Count: 323
>>> m_count(10)
Count: 835
>>> m_count(11)
Count: 2188
>>> m_count(12)
Count: 5798
>>> m_count(13)
Count: 15511
>>> m_count(14)
Count: 41835
>>> m_count(15)
Count: 113634
To exit interactive Python use
quit()
Notes on duplicates
The way I learned about Motzkin numbers was by hand enumerating the trees with pen and paper and finding a duplicate by using the method of adding a unary branch to the preceding trees M(N-1) and binary branches to the preceding preceding M(N-2) trees.
This one tree was generated twice for M(5) from M(4) trees
(b (u t) (u t))
the first by adding a unary branch to
(b (u t) t)
and second by adding a unary branch to
(b t (u t))
After doing this I had the sequence of numbers 1,2,4,9,21 which I used with a OEIS search and the top result was A001006 for Motzkin numbers. Once I had the larger list of Motzkin numbers I used the Prolog code to generate the counts for the larger input values and they all agreed. Now you can add OEIS to your programming tool box with a valid example to demonstrate to others.
The bigger picture
If you have read this far then you probably see that this is part of a bigger problem which is building a system first in Prolog that can use term rewriting to solve math expressions up to basic calculus but more importantly show the steps taken. So this gets one part of the way toward generating binary expression trees to be used as test cases. The next step is to be able to set individually the number of nodes that are unary and binary instead of having them fixed by the Motzkin number. I only used the Motzkin numbers to verify that I was generating a subset of the combinations correctly. Now that I have the pattern for that I can modify it to accept one argument for the number of unary nodes and one for the binary nodes. See: How to enumerate combinations using DCGs with CLP(FD) and multiple constraints
Only when I get stuck will I ask a questions related to this, so don't expect to see all of the necessary bread crumbs.
Prolog output
?- length(Ls, N), phrase(e, Ls).
L
