Mejora de algoritmos para enumerar árboles binarios

Question

Mar 06, 2017, 02:43 PM

language-agnostic binary-tree algorithm oeis motzkin-numbers

Mejora de algoritmos para enumerar árboles binarios

Actualmente puedo enumerar arraigado planar sin etiqueta árboles binarios usando el siguiente código de Prólogo de fuerza bruta.

e --> u | b | t.
u --> ['[op(u),['], e, [']]'].
b --> ['[op(b),['], e, [','], e, [']]'].
t --> ['number(n)'].

Nota: Vea los listados de salida a continuación.

y generarlos en tamaño creciente usando

es(S) :-
    length(Ls, _),
    phrase(e, Ls),     % or e(Ls,[]),
    atomic_list_concat(Ls,S).

Sin embargo, este es un algoritmo de fuerza bruta ineficiente.

Existe un algoritmo más eficiente para enumerar árboles binarios planos sin etiquetar enraizados?

Nota: Los árboles se pueden generar utilizando los árboles de las dos iteraciones anteriores, piense en los números de Fibonacci y agregue una rama unaria o una rama binaria, sin embargo, esto conduce a árboles duplicados. Yo mismo podría hacer esa versión, lo que estoy buscando es un algoritmo que genere los árboles de manera eficiente la primera vez sin duplicados.

Nota: Un árbol binario también se conoce como árbol de expresiones binarias o un K-ary tree con K <= 2.

Suplement Resultados

Mi versión de fuerza bruta para M (15) tomó 1 hora y 27 minutos, mientras que la versión eficiente para M (15) tomó aproximadamente 2 segundos.

bviamente, el algoritmo eficiente es solo eso, mucho más eficiente y por qué hice la pregunta.

Motzkin números

El número de árboles que tienenNos nodos @ para un árbol binario sin etiqueta plano enraizado están dados por los números de Motzkin. Ver: OEIS A001006

Nodes  Trees
1      1
2      1
3      2
4      4
5      9

El número de árboles que tienen N nodos internos para un árbol binario sin etiqueta plano enraizado viene dado por números catalanes. Existe un algoritmo más eficiente para generar árboles binarios planos enraizados utilizando números catalanes.

Nota
El número de árboles basados en números catalanes don tienen ramas unarias y cuentan solointern nodos.

mientra

el número de árboles según los números de Motzkinhace tiene ramas unarias y cuentatodo nodos.

Ver
OEIS A000108
Catalan Numbers por Tom Davis

Relacionar elementos de la lista de Prolog con el número de Motzkin

% M is Motzkin number, N is number of  list elements passed to atomic_list_concat\2
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).

Estadísticas con versión ineficiente de fuerza bruta

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.

Referencias

Un libro descargable gratuito como PDF que podría ayudar es "Combinatoria analítica" por Philippe Flajolet y Robert Sedgewick

También vea las referencias en elCatalá etiqueta.

Motzkin números

BNF

<expression> ::= 
      <unary expression>
    | <binary expression>
    | <terminal>

<unary expression> ::= 
    "(u" <expression> ")"

<binary expression> ::= 
    "(b" <expression> " " <expression> ")"

<terminal> ::= 
    "t"

Utilizandoresponde por David Eisenstat

Piense en esto como notas, o migas de pan, para mí en caso de que necesite usar esto nuevamente en muchos meses después de que lo olvide.

Para probar la respuesta, utilicé WSL (Subsistema de Windows para Linux) con Python 3 instalado

Usando Windows 10 creé un archivo llamadomotzkin.py en el directorio

C:\Users\Eric\Documents\Prolog

con el código Python

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 en WSL creé un enlace simbólico al directorio de Windows Prolog

$ ln -s "/mnt/c/Users/Eric/Documents/Prolog" /home/eric/Prolog

y cambió al directorio WSL Prolog

$ cd Prolog

then comenzó Python3

~/Prolog$ python3

e importó el código Python

>>> import motzkin

y ejecutó lo siguiente con el argumento de que ubtrees es el número Motzkin

>>> 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)

y para verificar los números de Motzkin

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

Para salir de Python interactivo use

quit()

Notas en duplicados

La forma en que aprendí acerca de los números de Motzkin fue enumerando a mano los árboles con lápiz y papel y encontrando un duplicado mediante el método de agregar una rama unaria a los árboles M (N-1) anteriores y ramas binarias a la M precedente anterior ( N-2) árboles.

ste árbol se generó dos veces para M (5) a partir de M (4) árboles

(b (u t) (u t))

the primero agregando una rama unaria a

(b (u t) t)

y segundo agregando una rama unaria a

(b t (u t))

espués de hacer esto, tuve la secuencia de números 1,2,4,9,21 que usé con unOEIS search y el resultado superior fue A001006 para los números de Motzkin. Una vez que tuve la lista más grande de números de Motzkin, usé el código Prolog para generar los recuentos de los valores de entrada más grandes y todos estuvieron de acuerdo. Ahora puede agregar OEIS a su caja de herramientas de programación con un ejemplo válido para demostrar a los demás.

La fotografía más grand

Si ha leído hasta aquí, probablemente vea que esto es parte de un problema mayor que consiste en construir un sistema primero en Prolog que puede usar la reescritura de términos para resolver expresiones matemáticas hasta el cálculo básico, pero lo más importante es mostrar los pasos dados. Entonces, esto es una parte del camino hacia la generación de árboles de expresión binaria para ser utilizados como casos de prueba. El siguiente paso es poder establecer individualmente el número de nodos que son unarios y binarios en lugar de tenerlos fijados por el número de Motzkin. Solo usé los números de Motzkin para verificar que estaba generando un subconjunto de las combinaciones correctamente. Ahora que tengo el patrón para eso, puedo modificarlo para aceptar un argumento para el número de nodos unarios y uno para los nodos binarios. Ver:Cómo enumerar combinaciones usando DCG con CLP (FD) y restricciones múltiples

Sólo cuando me quede atascado, haré preguntas relacionadas con esto, así que no esperes ver todas las migas de pan necesarias.

Salida de Prolog

?- length(Ls, N), phrase(e, Ls).
Ls = ['number(0)'],
N = 1 ;
Ls = ['[op(u),[', 'number(0)', ']]'],
N = 3 ;
Ls = ['[op(u),[', '[op(u),[', 'number(0)', ']]', ']]'],
N = 5 ;
Ls = ['[op(b),[', 'number(0)', ',', 'number(0)', ']]'],
N = 5 ;
Ls = ['[op(u),[', '[op(u),[', '[op(u),[', 'number(0)', ']]', ']]', ']]'],
N = 7 ;
Ls = ['[op(u),[', '[op(b),[', 'number(0)', ',', 'number(0)', ']]', ']]'],
N = 7 ;
Ls = ['[op(b),[', '[op(u),[', 'number(0)', ']]', ',', 'number(0)', ']]'],
N = 7 ;
Ls = ['[op(b),[', 'number(0)', ',', '[op(u),[', 'number(0)', ']]', ']]'],
N = 7 ;

?- es(S).
S = 'number(0)' ;
S = '[op(u),[number(0)]]' ;
S = '[op(u),[[op(u),[number(0)]]]]' ;
S = '[op(b),[number(0),number(0)]]' ;
S = '[op(u),[[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(u),[[op(b),[number(0),number(0)]]]]' ;
S = '[op(b),[[op(u),[number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[number(0)]]]]' ;
S = '[op(u),[[op(u),[[op(u),[[op(u),[number(0)]]]]]]]]' ;
S = '[op(u),[[op(u),[[op(b),[number(0),number(0)]]]]]]' ;
S = '[op(u),[[op(b),[[op(u),[number(0)]],number(0)]]]]' ;
S = '[op(u),[[op(b),[number(0),[op(u),[number(0)]]]]]]' ;
S = '[op(b),[[op(u),[[op(u),[number(0)]]]],number(0)]]' ;
S = '[op(b),[[op(u),[number(0)]],[op(u),[number(0)]]]]' ;
S = '[op(b),[[op(b),[number(0),number(0)]],number(0)]]' ;
S = '[op(b),[number(0),[op(u),[[op(u),[number(0)]]]]]]' ;
S = '[op(b),[number(0),[op(b),[number(0),number(0)]]]]' ;

?- es_m(1,E).
E = 'number(n)' ;
false.

?- es_m(2,E).
E = '[op(u),[number(n)]]' ;
false.

?- es_m(3,E).
E = '[op(u),[[op(u),[number(n)]]]]' ;
E = '[op(b),[number(n),number(n)]]' ;
false.

?- es_m(4,E).
E = '[op(u),[[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(u),[[op(b),[number(n),number(n)]]]]' ;
E = '[op(b),[[op(u),[number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[number(n)]]]]' ;
false.

?- es_m(5,E).
E = '[op(u),[[op(u),[[op(u),[[op(u),[number(n)]]]]]]]]' ;
E = '[op(u),[[op(u),[[op(b),[number(n),number(n)]]]]]]' ;
E = '[op(u),[[op(b),[[op(u),[number(n)]],number(n)]]]]' ;
E = '[op(u),[[op(b),[number(n),[op(u),[number(n)]]]]]]' ;
E = '[op(b),[[op(u),[[op(u),[number(n)]]]],number(n)]]' ;
E = '[op(b),[[op(u),[number(n)]],[op(u),[number(n)]]]]' ;
E = '[op(b),[[op(b),[number(n),number(n)]],number(n)]]' ;
E = '[op(b),[number(n),[op(u),[[op(u),[number(n)]]]]]]' ;
E = '[op(b),[number(n),[op(b),[number(n),number(n)]]]]' ;
false.