Énumérer les arbres binaires

20

Arbres binaires

Un arbre binaire est un arbre avec des nœuds de trois types:

nœuds terminaux, qui n'ont pas d'enfants
nœuds unaires, qui ont chacun un enfant
nœuds binaires, qui ont chacun deux enfants

Nous pouvons les représenter avec la grammaire suivante, donnée en BNF (forme Backus – Naur):

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

<terminal> ::= 
    "0"

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

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

Dans cette grammaire, les nœuds sont donnés en précommande et chaque nœud est représenté par un chiffre qui est le nombre d'enfants qu'il a.

Numéros Motzkin

Les nombres de Motzkin ( OEIS ) ( Wikipedia ) ont de nombreuses interprétations, mais une interprétation est que le nnombre de Motzkin est le nombre d'arbres binaires distincts avec des nnœuds. Un tableau des nombres Motzkin commence

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

par exemple, M(5)est 9, et les neuf arbres binaires distincts avec 5 nœuds sont

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)

Tâche

Prenez un seul entier positif nen entrée et sortez tous les arbres binaires distincts avec des nnœuds.

Exemples nde 1 à 5 avec parenthèses incluses pour plus de lisibilité

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)

Contribution

L'entrée sera un entier positif.

Production

La sortie doit être une représentation intelligible des arbres binaires distincts avec autant de nœuds. Il n'est pas obligatoire d'utiliser la chaîne exacte donnée par la grammaire BNF ci-dessus: il suffit que la syntaxe utilisée donne une représentation non ambiguë des arbres. Par exemple, vous pouvez utiliser []au lieu de (), un niveau supplémentaire de crochets [[]]au lieu de[] , des parenthèses externes sont présentes ou manquantes, des virgules supplémentaires ou aucune virgule, des espaces supplémentaires, des parenthèses ou aucune parenthèse, etc.

Tous ces éléments sont équivalents:

(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

Également une variation proposée par @xnor dans un commentaire. Puisqu'il existe un moyen de traduire cela dans un format qui peut être compris, il est acceptable.

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

Pour rendre cela plus facile à comprendre convertir certains des []à ()comme si

[([])()]

Maintenant, si vous commencez par

[]

puis insérez un binaire qui a besoin de deux expressions que vous obtenez

 [()()] which is 2

puis pour le premier () insérer un unaire qui a besoin d'une expression que vous obtenez

 [([])()] which is 21

mais puisque []ou ()sans crochets intérieurs peut représenter 0 qui n'a plus besoin d'expressions, vous pouvez l'interpréter comme

Notez que les réponses devraient fonctionner théoriquement avec une mémoire infinie, mais manqueront évidemment de mémoire pour une entrée finie dépendante de l'implémentation.

Variations de sortie

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 endroit possible pour vérifier les arbres en double

Un endroit pour vérifier un doublon est avec M (5).
Cet arbre a été généré deux fois pour M (5) à partir de M (4) arbres

(2 (1 0) (1 0))

le premier en ajoutant une branche unaire à

(2 (1 0) 0)

et deuxièmement en ajoutant une branche unaire à

(2 0 (1 0))

Comprendre BNF

La BNF est composée de règles simples:

<symbol> ::= expression

où à gauche se trouve un nom de symbole entouré <>.
À droite, l'expression de construction du symbole. Certaines règles utilisent d'autres règles dans la construction, par exemple

<e> ::= <terminal>

e peut être un terminal

et certaines règles ont des caractères qui sont utilisés dans la construction du symbole, par exemple

<terminal> ::= "0"

terminal est juste le caractère zéro.

Certaines règles ont plusieurs façons de les construire, par exemple

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

Un epeut être un <terminal>ou un <unary>ou un <binary>.

Et certaines règles sont une séquence de parties, par exemple

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

A unaryest les caractères (1suivis de ce qui peut être construit pour esuivi de ).

Vous commencez toujours par la règle de départ, qui pour cela <e>.

Quelques exemples simples:

La séquence la plus simple est juste 0. Nous commençons donc avec la règle de départ <e>et voyons qu'il y a trois choix:

  <terminal>   
| <unary>
| <binary>

alors prenez le premier <terminal>. Maintenant, un terminal n'a pas le choix et l'est 0. Remplacez donc <terminal>par 0dans la <e>règle et vous avez terminé.

Ensuite, le suivant est (1 0). Commencez avec <e>et utilisez la règle <unary>qui a

"(1" <e> ")"

Maintenant, cela nécessite un <e>donc nous revenons à <e>et faisons un choix de l'un des trois, cette fois en choisissant, <terminal>ce qui donne 0. Le remplacement 0en (1 <e> )donne (1 0), et il est remplacé en <unary>si <e>est (1 0).

code-golf graph-theory binary-tree Guy Coder
la source

Alors, un arbre binaire? "un arbre binaire est une structure de données arborescente dans laquelle chaque nœud a au plus deux enfants"

fəˈnɛtɪk

3

Votre description est celle d'un arbre binaire. Les arbres binaires n'ont pas besoin d'avoir 2 enfants. Cela signifie simplement qu'ils ont au plus 2 enfants. Je suppose que unaire-binaire est juste un terme plus spécifique qui ne signifie vraiment rien de différent.

fəˈnɛtɪk

Pensez à clarifier ce qu'est "BNF" pour ceux d'entre nous qui ne sont pas des informaticiens

Luis Mendo

1

@GuyCoder Mon point est que si quelqu'un voit "BNF" et ne sait pas ce que cela signifie, il peut être repoussé et arrêter de lire. Peut-être que l'utilisation du nom au lieu de l'acronyme et l'ajout d'un lien vers Wikipedia suffiraient

Luis Mendo

4

@ mbomb007 Le nom a été modifié. Je devrais obtenir un prix de pression des pairs pour cela. :)

Guy Coder

12

Haskell, 68 octets

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

Les nœuds terminaux sont représentés par 0, les nœuds unaires et binaires par (e)resp. (ee), donc les deux arbres à trois nœuds sont donnés comme (00)et ((0)).

Exemples:

*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

Christian Sievers
la source

5

CJam (37 octets)

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

Démo en ligne . Notez que ce n'est pas très efficace et que vous ne voulez probablement pas essayer de calculer l'entrée en 5ligne.

Dissection à suivre.

Peter Taylor
la source

5

Pyth ( 24 21 19 octets)

Ceci est basé sur ma solution Python 3 .

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

C'est ma première utilisation de Pyth, donc c'est probablement encore jouable au golf.

Exemple , sortie lorsque l'entrée est 4:

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

1 représente un nœud binaire, 0 représente un nœud unaire et -1 représente un nœud terminal. Il y a un nœud terminal implicite à la fin de chaque arbre.

Explication :

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
la source

Intéressant: code source Pyth

Guy Coder

4

brainfuck, 107 octets

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

Formaté:

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

Essayez-le en ligne

L'entrée est prise comme un octet et l'arborescence 12100est représentée comme \x01\x02\x03\x02suit: pour convertir en arrière, traduire tr/\x01\x02\x03/012/, inverser la chaîne et ajouter une finale 0. Les arbres sont séparés par \xfe. (La sortie peut être rendue plus facile à lire en changeant par exemple le premier -en -36et le .en +47.-47, où -36signifie une chaîne de 36 -caractères, etc.)

Cette approche utilise la propriété (que Ben Frankel a également utilisée): en considérant les nœuds possibles comme -1, 0, 1et sans tenir compte du -1nœud final , une liste représente un arbre valide si et seulement si (1) tous les préfixes de la liste ont une somme non négative, et (2) la somme de la liste entière est égale à0 . La première condition est conservée lors de la génération de nœuds intermédiaires, donc seule la deuxième condition doit être vérifiée à la fin.

La bande est divisée en cellules à 5 nœuds,

i d x 0 0

où iest l'indice (descendant de gauche à droite), dest la somme partielle et xest l'élément.

Croquis du flux de contrôle:

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)

Notez que parfois une valeur est stockée ou initialisée comme étant un ou deux supérieure à la valeur réelle (conceptuelle) et ajustée selon les besoins.

Mitch Schwartz
la source

3

Python 3 ( 138 134 128 128 121 119 octets)

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

Exemple de sortie, pour 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 représente un nœud binaire, 0 représente un nœud unaire et -1 représente un nœud terminal. Il y a un nœud terminal implicite à la fin de chaque arbre.

Le programme commence à prendre trop de temps aux alentours n=17.

Ben Frankel
la source

3

JavaScript (Firefox 30-57), 79 octets

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]]:[[]]

Où -1représente un terminal, 0un nœud unaire et 1un nœud binaire. Commence à ralentir m=14sur mon PC. Fonctionne récursivement depuis la fin de l'arborescence.

Le nombre de nœuds non comptabilisés lest limité par le fait qu'il ne peut rester qu'un seul nœud à la fin.
Le type du nœud suivant nest limité par la nécessité d'avoir suffisamment de nœuds non comptabilisés pour être ses enfants.

Neil
la source

2

Prolog, 149 144 138 137 137 131 107 octets

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

Et pour compter les solutions

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
la source

1

Python, 71 octets

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

Cela représente les arbres comme des tuples imbriqués tels que ((((),), ()),), qui peuvent être transformés en ((())())en supprimant les virgules, les espaces et les éléments les plus externes ().

Une version antérieure de 76 octets:

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