Enumerar árvores binárias

20

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

Guy Coder
fonte
Então, uma árvore binária? "uma árvore binária é uma estrutura de dados em árvore em que cada nó tem no máximo dois filhos"
fənɛtɪk
3
Sua descrição é a de uma árvore binária. Árvores binárias não precisam ter 2 filhos. Significa apenas que eles têm no máximo 2 filhos. Eu acho que unário-binário é apenas um termo mais específico que realmente não significa nada diferente.
58517
Considere esclarecer o que "BNF" é para aqueles de nós que não são cientistas da computação
Luis Mendo
1
@GuyCoder Meu argumento é que, se alguém vê "BNF" e não sabe o que isso significa, pode ser adiado e parar de ler. Talvez usando o nome em vez da sigla e adicionando um link para a Wikipedia seria suficiente
Luis Mendo
4
@ mbomb007 Nome alterado. Eu deveria receber um prêmio por pressão dos colegas por isso. :)
Guy Coder

Respostas:

12

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 
Peneiradores cristãos
fonte
5

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.

Peter Taylor
fonte
5

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.
Ben Frankel
fonte
De interesse: Código-fonte Pyth
Guy Coder
4

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.

Mitch Schwartz
fonte
3

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.

Ben Frankel
fonte
3

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.
Neil
fonte
2

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 
Guy Coder
fonte
1

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['']
Mitch Schwartz
fonte
1

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.

Esolanging Fruit
fonte