Enumerar árboles binarios

Arboles binarios

Un árbol binario es un árbol con nodos de tres tipos:

• nodos terminales, que no tienen hijos
• nodos unarios, que tienen un hijo cada uno
• nodos binarios, que tienen dos hijos cada uno

Podemos representarlos con la siguiente gramática, dada en BNF (forma Backus-Naur):

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

<terminal> ::= 
    "0"

<unary> ::= 
    "(1" <e> ")"

<binary> ::= 
    "(2" <e> " " <e> ")"

En esta gramática, los nodos se dan en preorden y cada nodo está representado por un dígito que es el número de hijos que tiene.

Números Motzkin

Los números de Motzkin ( OEIS ) ( Wikipedia ) tienen muchas interpretaciones, pero una interpretación es que el nnúmero de Motzkin es el número de árboles binarios distintos con nnodos. Comienza una tabla de números de Motzkin

N          Motzkin number M(N)
1          1
2          1
3          2 
4          4 
5          9 
6         21 
7         51 
8        127 
    ...

por ejemplo, M(5)es 9, y los nueve árboles binarios distintos con 5 nodos son

1      (1 (1 (1 (1 0))))  
2      (1 (1 (2 0 0)))  
3      (1 (2 0 (1 0)))  
4      (1 (2 (1 0) 0))  
5      (2 0 (1 (1 0)))  
6      (2 0 (2 0 0))  
7      (2 (1 0) (1 0))  
8      (2 (1 (1 0)) 0)  
9      (2 (2 0 0) 0)  

Tarea

Tome un solo entero positivo ncomo entrada y salida de todos los árboles binarios distintos con nnodos.

Ejemplos nde 1 a 5 con paréntesis incluidos para facilitar la lectura

0

(1 0)

(1 (1 0))
(2 0 0)

(1 (1 (1 0)))
(1 (2 0 0))
(2 0 (1 0))
(2 (1 0) 0)

(1 (1 (1 (1 0))))
(1 (1 (2 0 0)))
(1 (2 0 (1 0)))
(1 (2 (1 0) 0))
(2 0 (1 (1 0)))
(2 0 (2 0 0))
(2 (1 0) (1 0))
(2 (1 (1 0)) 0)
(2 (2 0 0) 0)

Entrada

La entrada será un entero positivo.

Salida

El resultado debe ser una representación inteligible de los distintos árboles binarios con tantos nodos. No es obligatorio usar la cadena exacta dada por la gramática BNF anterior: es suficiente que la sintaxis utilizada dé una representación inequívoca de los árboles. Por ejemplo, podría usar en []lugar de ()un nivel adicional de paréntesis en [[]]lugar de []paréntesis externos presentes o faltantes, comas adicionales o sin comas, espacios adicionales, paréntesis o sin paréntesis, etc.

Todos estos son equivalentes:

(1 (2 (1 0) 0))  
[1 [2 [1 0] 0]]  
1 2 1 0 0  
12100  
(1 [2 (1 0) 0])  
.:.--  
*%*55  
(- (+ (- 1) 1))
-+-11

También una variación propuesta por @xnor en un comentario. Como hay una manera de traducir esto a un formato que se pueda entender, es aceptable.

[[[]][]]  is (2 (1 0) 0)

Para que sea más fácil de entender, convierta algunos de los []que le ()gusten

[([])()]

Ahora si comienzas con

[]

luego inserta un binario que necesita dos expresiones que obtienes

 [()()] which is 2

y luego para el primer () inserta un unario que necesita una expresión que obtienes

 [([])()] which is 21

pero como []o ()sin corchetes internos puede representar 0 que no necesita más expresiones, puede interpretarlo

 2100

Tenga en cuenta que las respuestas deberían funcionar teóricamente con memoria infinita, pero obviamente se quedarán sin memoria para una entrada finita dependiente de la implementación.

Variaciones de salida

BNF             xnor       Christian   Ben
b(t, b(t, t))   [{}{{}{}}] (0(00))     (1, -1, 1, -1)                         
b(t, u(u(t)))   [{}{(())}] (0((0)))    (1, -1, 0, 0)           
b(u(t), u(t))   [{()}{()}] ((0)(0))    (1, 0, -1, 0)                     
b(b(t, t), t)   [{{}{}}{}] ((00)0)     (1, 1, -1, -1)              
b(u(u(t)), t)   [{(())}{}] (((0))0)    (1, 0, 0, -1)                          
u(b(t, u(t)))   [({}{()})] ((0(0)))    (0, 1, -1, 0)                          
u(b(u(t), t))   [({()}{})] (((0)0))    (0, 1, 0, -1)                        
u(u(b(t, t)))   [(({}{}))] (((00)))    (0, 0, 1, -1)                          
u(u(u(u(t))))   [(((())))] ((((0))))   (0, 0, 0, 0)  

Un posible lugar para buscar árboles duplicados

Un lugar para buscar un duplicado es con M (5).
Este árbol se generó dos veces para M (5) a partir de M (4) árboles

(2 (1 0) (1 0))  

el primero agregando una rama unaria a

(2 (1 0) 0)

y segundo agregando una rama unaria a

(2 0 (1 0))

Entendiendo BNF

BNF se compone de reglas simples:

<symbol> ::= expression

donde a la izquierda hay un nombre de símbolo rodeado por <>.
A la derecha está la expresión para construir el símbolo. Algunas reglas usan otras reglas en la construcción, por ej.

<e> ::= <terminal>

e puede ser un terminal

y algunas reglas tienen caracteres que se usan para construir el símbolo, por ej.

<terminal> ::= "0"

terminal es solo el caracter cero.

Algunas reglas tienen múltiples formas de construirlas, p. Ej.

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

Un epuede ser a <terminal>o a <unary>o a <binary>.

Y algunas reglas son una secuencia de partes, por ej.

<unary> ::= "(1" <e> ")"

A unaryson los caracteres (1seguidos de lo que se puede construir eseguido de ).

Siempre comienza con la regla de inicio, que para esto <e>.

Algunos ejemplos simples:

La secuencia más simple es justa 0. Entonces comenzamos con la regla de inicio <e>y vemos que hay tres opciones:

  <terminal>   
| <unary>
| <binary>

así que toma el primero <terminal>. Ahora una terminal no tiene opciones y es 0. Así que reemplace <terminal>con 0en la <e>regla y ya está.

Entonces el siguiente es (1 0). Comience con <e>y use la regla <unary>que tiene

"(1" <e> ")"

Ahora esto necesita un, <e>así que volvemos <e>y hacemos una elección de uno de los tres, esta vez eligiendo, lo <terminal>que da 0. Reemplazar 0en (1 <e> )da (1 0), y esto se reemplaza en <unary>así <e>es (1 0).

Haskell, 68 bytes

t 0=[""]
t 1=["0"]
t n=['(':x++y++")"|k<-[1..n-1],x<-t k,y<-t$n-k-1]

Los nodos terminales están representados por nodos 0unarios y binarios por (e)resp. (ee), por lo que los dos árboles de tres nodos se dan como (00)y ((0)).

Ejemplos:

*Main> t 5
["(0(00))","(0((0)))","((0)(0))","((00)0)","(((0))0)","((0(0)))","(((0)0))","(((00)))","((((0))))"]
*Main> length $ t 8
127
*Main> length $ t 15
113634 

CJam (37 bytes)

0aa{_2m*2\f+1Y$f+++:e__&}qi:A*{,A=},p

Demo en línea . Tenga en cuenta que esto no es muy eficiente, y probablemente no quiera intentar calcular la entrada en 5línea.

Disección a seguir.

Pyth ( 24 21 19 bytes)

Esto se basa en mi solución Python 3 .

f!|sTf<sY0._T^}1_1t

Es la primera vez que uso Pyth, por lo que es probable que todavía sea golfable.

Ejemplo , salida cuando la entrada es 4:

[[1, 0, -1], [1, -1, 0], [0, 1, -1], [0, 0, 0]]

1 representa un nodo binario, 0 representa un nodo unario y -1 representa un nodo terminal. Hay un nodo terminal implícito al final de cada árbol.

Explicacion :

f!|sTf<sY0._T^}1_1t
f                    filter
             ^    t  length n-1 lists of elements
              }1_1   from [1, 0, -1]
 !|                  for when both
   sT                sum of list is 0, and
     f    ._T        for each prefix of list,
      <sY0           sum of prefix is non-negative.

brainfuck, 107 bytes

,>++>-[-[<-[<-[>>[[>+<-]<]>+>[[<+>>>>>+<<<<-]>]>>++>,++++>]>[<+>-[+>>]>[<->[.<<<
<<]+[->+]+>>>]]]]<[[,<]<]<]

Formateado:

,>++>-
[
  -
  [
    <-
    [
      <-
      [
        >>
        [[>+<-]<]
        >+>
        [[<+> >>>>+<<<<-]>]
        >>++>,++++>
      ]
      >
      [
        <+>-
        [
          +>>
        ]
        >
        [
          <->[.<<<<<]
          +[->+]
          +>>>
        ]
      ]
    ]
  ]
  <
  [
    [,<]
    <
  ]
  <
]

Pruébalo en línea

La entrada se toma como un byte y el árbol 12100se representa como \x01\x02\x03\x02: para volver a convertir, traducir tr/\x01\x02\x03/012/, invertir la cadena y agregar un final 0. Los árboles están separados por \xfe. (La salida se puede hacer más fácil de leer, por ejemplo, cambiando el primero -en -36y el .en +47.-47, donde -36significa una cadena de 36 -caracteres, etc.)

Este enfoque hace uso de la propiedad (que también utilizó Ben Frankel): considerando los posibles nodos como -1, 0, 1y sin tener en cuenta el -1nodo final , una lista representa un árbol válido si y solo si (1) todos los prefijos de la lista tienen una suma no negativa, y (2) la suma de la lista completa es igual 0. La primera condición se mantiene al generar nodos intermedios, por lo que solo la segunda condición debe verificarse al final.

La cinta se divide en celdas de 5 nodos,

i d x 0 0

donde iestá el índice (descendiendo de izquierda a derecha), des la suma parcial y xes el elemento.

Bosquejo del flujo de control:

take n and push initial node
while stack is non-empty:
    if rightmost node can be decremented:
        decrement rightmost node
        if there are less than n nodes:
            push new node
        else if valid tree:
            print
    else:
        backtrack (pop)

Tenga en cuenta que a veces un valor se almacena o inicializa como uno o dos mayor que el valor real (conceptual) y se ajusta según sea necesario.

Python 3 ( 138 134 128 121 119 bytes)

from itertools import*
lambda n:[any(sum(t[:k])<0for k in range(n))|sum(t)or print(t)for t in product(*[[-1,0,1]]*~-n)]

Ejemplo de salida, para n=5:

(0, 0, 0, 0)
(0, 0, 1, -1)
(0, 1, -1, 0)
(0, 1, 0, -1)
(1, -1, 0, 0)
(1, -1, 1, -1)
(1, 0, -1, 0)
(1, 0, 0, -1)
(1, 1, -1, -1)

1 representa un nodo binario, 0 representa un nodo unario y -1 representa un nodo terminal. Hay un nodo terminal implícito al final de cada árbol.

El programa comienza a tomar demasiado tiempo n=17.

JavaScript (Firefox 30-57), 79 bytes

f=(m,l=0)=>m?[for(n of[1,0,-1])if(l>n&l<=m+n)for(a of f(m-1,l-n))[...a,n]]:[[]]

Donde -1representa un terminal, 0un nodo unario y 1un nodo binario. Comienza a ser lento en m=14mi PC. Recursivamente trabaja desde el final del árbol.

• El número de nodos no contabilizados lestá limitado por el hecho de que solo puede quedar 1 nodo al final.
• El tipo del siguiente nodo nestá limitado por la necesidad de tener suficientes nodos no contabilizados para ser sus hijos.

Prolog, 149 144 138 137 131 107 bytes

e(L,L)-->[0].

e([_|A],L)--> 
    [1],
    e(A,L).

e([_,_|A],L)--> 
    [2],
    e(A,B), 
    e(B,L).

e(M,E):-                   
    length([_|L],M),        
    e(L,[],E,[]).           

?- e(5,S).
S = [1, 1, 1, 1, 0] ;
S = [1, 1, 2, 0, 0] ;
S = [1, 2, 0, 1, 0] ;
S = [1, 2, 1, 0, 0] ;
S = [2, 0, 1, 1, 0] ;
S = [2, 0, 2, 0, 0] ;
S = [2, 1, 0, 1, 0] ;
S = [2, 1, 1, 0, 0] ;
S = [2, 2, 0, 0, 0].

Y para contar las soluciones

e_count(N,Count) :-
    length([_|Ls], N),
    findall(., phrase(e(Ls,[]),E), Sols),
    length(Sols, Count).

?- e_count(N,Count).
N = Count, Count = 1 ;
N = 2, Count = 1 ;
N = 3, Count = 2 ;
N = Count, Count = 4 ;
N = 5, Count = 9 ;
N = 6, Count = 21 ;
N = 7, Count = 51 ;
N = 8, Count = 127 ;
N = 9, Count = 323 ;
N = 10, Count = 835 ;
N = 11, Count = 2188 ;
N = 12, Count = 5798 ;
N = 13, Count = 15511 ;
N = 14, Count = 41835 ;
N = 15, Count = 113634 

Python, 71 bytes

f=lambda n:{(a+b,)for k in range(n)for a in f(k)for b in f(n+~k)}or[()]

Esto representa los árboles como tuplas anidadas, como ((((),), ()),), que se pueden transformar ((())())eliminando comas, espacios y lo más externo ().

Una versión anterior de 76 bytes:

f=lambda n:{'('+a+b+')'for k in range(n)for a in f(k)for b in f(n+~k)}or['']

CJam, 38 bytes

Utiliza un enfoque diferente que la respuesta CJam de Peter Taylor.

3rim*{:(1\+[{1$+}*])\:(_:z#|!},

La salida será algo así 1110120020102100. Cada árbol es un grupo de ndígitos (donde nestá el número de entrada).

La idea básica es que generamos cada posible cadena de dígitos 0, 1y 2, a continuación, filtrar sólo los que son árboles bien formados.