language agnostic - Algorithm improvement for enumerating binary trees

Question

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

Answer 1

In addition to the solution that is already posted, I would like to present the following Prolog solution for the task.

First, here is a declarative description of such trees:

e(number)        --> [].
e(u(Arg))        --> [_], e(Arg).
e(b(Left,Right)) --> [_,_], e(Left), e(Right).

I am also using a dcg. However, I am using it for a different purpose than in the question: In my case, I only describe a list in order to limit the depth of solutions. Think of the nonterminals as stating how many "tokens" will definitely be consumed by applying a rule. Note also that I am using compound terms to naturally describe such trees.

Sample query, using iterative deepening:

?- length(Ls, _), phrase(e(E), Ls).
Ls = [],
E = number ;
Ls = [_5710],
E = u(number) ;
Ls = [_5710, _5716],
E = u(u(number)) ;
Ls = [_5710, _5716],
E = b(number, number) ;
Ls = [_5710, _5716, _5722],
E = u(u(u(number))) .

I can now count solutions as follows:

es_count(M, Count) :-
        length([_|Ls], M),
        findall(., phrase(e(_), Ls), Sols),
        length(Sols, Count).

Here are a few more solutions:

?- length(_, M),
   time(es_count(M, Count)),
   portray_clause(m_count(M,Count)),
   false.
% 7 inferences, 0.000 CPU in 0.000 seconds (64% CPU, 636364 Lips)
% 28 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 1120000 Lips)
m_count(1, 1).
% 29 inferences, 0.000 CPU in 0.000 seconds (31% CPU, 1318182 Lips)
m_count(2, 1).
% 33 inferences, 0.000 CPU in 0.000 seconds (76% CPU, 1736842 Lips)
m_count(3, 2).
% 41 inferences, 0.000 CPU in 0.000 seconds (81% CPU, 1952381 Lips)
m_count(4, 4).
% 61 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 2178571 Lips)
m_count(5, 9).
% 109 inferences, 0.000 CPU in 0.000 seconds (91% CPU, 2595238 Lips)
m_count(6, 21).
% 230 inferences, 0.000 CPU in 0.000 seconds (93% CPU, 2948718 Lips)
m_count(7, 51).
% 538 inferences, 0.000 CPU in 0.000 seconds (97% CPU, 3221557 Lips)
m_count(8, 127).
% 1,337 inferences, 0.000 CPU in 0.000 seconds (99% CPU, 3293103 Lips)
m_count(9, 323).
% 3,434 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 3400000 Lips)
m_count(10, 835).
% 9,000 inferences, 0.003 CPU in 0.003 seconds (94% CPU, 3301541 Lips)
m_count(11, 2188).
% 23,908 inferences, 0.007 CPU in 0.024 seconds (31% CPU, 3300387 Lips)
m_count(12, 5798).
% 64,158 inferences, 0.019 CPU in 0.024 seconds (79% CPU, 3387792 Lips)
m_count(13, 15511).
% 173,579 inferences, 0.051 CPU in 0.062 seconds (83% CPU, 3397448 Lips)
m_count(14, 41835).
% 472,853 inferences, 0.139 CPU in 0.152 seconds (92% CPU, 3393690 Lips)
m_count(15, 113634).

Prolog is a nice language for generating solutions exhaustively based on declarative descriptions!