Enumerar árvores binárias

Árvores binárias

Uma árvore binária é uma árvore com nós de três tipos:

• nós terminais, que não têm filhos
• nós unários, que têm um filho cada
• nós binários, que têm dois filhos cada

Podemos representá-los com a seguinte gramática, dada em BNF (forma Backus – Naur):

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

<terminal> ::= 
    "0"

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

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

Nesta gramática, os nós são fornecidos em pré-encomenda e cada nó é representado por um dígito, que é o número de filhos que possui.

Números de Motzkin

Os números de Motzkin ( OEIS ) ( Wikipedia ) têm muitas interpretações, mas uma interpretação é que o nnúmero de Motzkin é o número de árvores binárias distintas com nnós. Uma tabela de números de Motzkin começa

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

por exemplo, M(5)é 9 e as nove árvores binárias distintas com 5 nós são

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)  

Tarefa

Pegue um número inteiro positivo único ncomo entrada e saída de todas as árvores binárias distintas com nnós.

Exemplos nde 1 a 5 com parênteses incluídos para facilitar a leitura

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

A entrada será um número inteiro positivo.

Saída

A saída deve ser uma representação inteligível das distintas árvores binárias com tantos nós. Não é obrigatório usar a sequência exata dada pela gramática BNF acima: é suficiente que a sintaxe usada forneça uma representação inequívoca das árvores. Por exemplo, você pode usar em []vez de (), um nível extra de colchetes em [[]]vez de [], parênteses externos estão presentes ou ausentes, vírgulas extras ou sem vírgulas, espaços extras, parênteses ou sem parênteses, etc.

Todos estes são 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

Também uma variação proposta por @xnor em um comentário. Como existe uma maneira de traduzir isso para um formato que possa ser entendido, é aceitável.

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

Para tornar isso mais fácil de entender, converta alguns dos []que ()quiserem

[([])()]

Agora, se você começar com

[]

depois insira um binário que precisa de duas expressões que você obtém

 [()()] which is 2

e depois para o primeiro () insira um unário que precise de uma expressão que você obtém

 [([])()] which is 21

mas como []ou ()sem bracketing interno pode representar 0, que não precisa de mais expressões, você pode interpretá-lo como

 2100

Observe que as respostas devem funcionar teoricamente com memória infinita, mas obviamente ficarão sem memória para uma entrada finita dependente da implementação.

Variações da produção

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)  

Um possível local para procurar árvores duplicadas

Um lugar para procurar uma duplicata é com M (5).
Essa árvore foi gerada duas vezes para M (5) a partir de M (4).

(2 (1 0) (1 0))  

o primeiro adicionando um ramo unário ao

(2 (1 0) 0)

e segundo adicionando um ramo unário ao

(2 0 (1 0))

Entendendo o BNF

O BNF é composto por regras simples:

<symbol> ::= expression

onde à esquerda é um nome de símbolo cercado por <>.
À direita está a expressão para construir o símbolo. Algumas regras usam outras regras na construção, por exemplo

<e> ::= <terminal>

e pode ser um terminal

e algumas regras têm caracteres que são usados ​​na construção do símbolo, por exemplo

<terminal> ::= "0"

terminal é apenas o caractere zero.

Algumas regras têm várias maneiras de construí-las, por exemplo

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

Um epode ser um <terminal>ou um <unary>ou um <binary>.

E algumas regras são uma sequência de partes, por exemplo

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

A unarysão os caracteres (1seguidos pelo que pode ser construído e eseguido por ).

Você sempre começa com a regra inicial, que para isso <e>.

Alguns exemplos simples:

A sequência mais simples é justa 0. Então começamos com a regra inicial <e>e vemos que há três opções:

  <terminal>   
| <unary>
| <binary>

então pegue o primeiro <terminal>. Agora, um terminal não tem opções e é 0. Então substitua <terminal>por 0na <e>regra e pronto.

Então o próximo é (1 0). Comece com <e>e use a regra <unary>que possui

"(1" <e> ")"

Agora, isso precisa de um, <e>para que voltemos <e>ae escolha um dos três, desta vez escolhendo, o <terminal>que dá 0. Substituir 0em (1 <e> )doações (1 0), e isso é substituído <unary>pelo que <e>é (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]

Nós terminais são representados por nós 0unários e binários por (e)resp. (ee), portanto, as duas árvores de três nós são fornecidas como (00)e ((0)).

Exemplos:

*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

Demonstração online . Observe que isso não é muito eficiente e você provavelmente não deseja tentar calcular a entrada 5online.

Dissecção a seguir.

Pitão ( 24 21 19 bytes)

Isso é baseado na minha solução Python 3 .

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

É a minha primeira vez usando Pyth, então isso provavelmente ainda é jogável.

Exemplo , saída quando a entrada é 4:

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

1 representa um nó binário, 0 representa um nó unário e -1 representa um nó terminal. Há um nó terminal implícito no final de cada árvore.

Explicação :

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

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

Formatado:

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

Experimente online

A entrada é aceita como um byte , e a árvore 12100é representada como \x01\x02\x03\x02: para converter de volta, converter tr/\x01\x02\x03/012/, inverter a sequência e adicionar uma final 0. As árvores são separadas por \xfe. (A saída pode ser mais fácil de ler, alterando, por exemplo, o primeiro -para dentro -36e o .para +47.-47, onde -36significa uma sequência de 36 -caracteres, etc.)

Essa abordagem utiliza a propriedade (que Ben Frankel também usou): considerando os possíveis nós -1, 0, 1e desconsiderando o -1nó final , uma lista representa uma árvore válida se e somente se (1) todos os prefixos da lista tiverem soma não negativa, e (2) a soma da lista inteira é igual 0. A primeira condição é mantida ao gerar nós intermediários, portanto, apenas a segunda condição precisa ser verificada no final.

A fita é dividida em células de 5 nós,

i d x 0 0

onde ié o índice (descendente da esquerda para a direita), dé a soma parcial e xé o elemento

Esboço do fluxo de controle:

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)

Observe que algumas vezes um valor é armazenado ou inicializado como um ou dois maiores que o valor real (conceitual) e ajustado conforme necessário.

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

Exemplo de saída, 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 um nó binário, 0 representa um nó unário e -1 representa um nó terminal. Há um nó terminal implícito no final de cada árvore.

O programa começa a demorar muito tempo 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]]:[[]]

Onde -1representa um terminal, 0um nó unário e 1um nó binário. Começa a ficar lento no m=14meu PC. Recursivamente trabalha de volta do final da árvore.

• O número de nós não contabilizados lé limitado pelo fato de que pode haver apenas 1 nó no final.
• O tipo do próximo nó né limitado pela necessidade de ter nós não contabilizados suficientes para serem seus filhos.

Prolog, 149 144 138 137 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].

E para contar as soluções

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[()]

Isso representa árvores como tuplas aninhadas, como ((((),), ()),), que podem ser transformadas ((())())removendo vírgulas, espaços e áreas externas ().

Uma versão 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

Usa uma abordagem diferente que a resposta CJam de Peter Taylor.

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

Saída será algo parecido 1110120020102100. Cada árvore é um grupo de ndígitos (onde nestá o número de entrada).

A idéia básica é que geramos cada possível seqüência de dígitos 0, 1e 2, em seguida, filtrar apenas os que são árvores bem formados.