Zählen Sie binäre Bäume auf

20

Binäre Bäume

Ein binärer Baum ist ein Baum mit drei Knotentypen:

Endknoten, die keine Kinder haben
unäre Knoten, die jeweils ein Kind haben
Binärknoten, die jeweils zwei untergeordnete Knoten haben

Wir können sie mit der folgenden Grammatik darstellen, die in BNF (Backus-Naur-Form) angegeben ist:

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

<terminal> ::= 
    "0"

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

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

In dieser Grammatik sind die Knoten in vorrangiger Reihenfolge angegeben, und jeder Knoten wird durch eine Ziffer dargestellt, die die Anzahl der Kinder angibt, die er hat.

Motzkin-Zahlen

Motzkin-Zahlen ( OEIS ) ( Wikipedia ) haben viele Interpretationen, aber eine Interpretation ist, dass die nth Motzkin-Zahl die Anzahl der verschiedenen Binärbäume mit nKnoten ist. Eine Tabelle mit Motzkin-Nummern beginnt

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

zB M(5)9, und die neun verschiedenen Binärbäumen mit 5 Knoten

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)

Aufgabe

Nehmen Sie eine einzelne positive Ganzzahl nals Eingabe und geben Sie alle unterschiedlichen Binärbäume mit nKnoten aus.

Beispiele für n1 bis 5 mit Klammern zur besseren Lesbarkeit

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)

Eingang

Die Eingabe ist eine positive ganze Zahl.

Ausgabe

Die Ausgabe sollte eine verständliche Darstellung der verschiedenen Binärbäume mit so vielen Knoten sein. Es ist nicht obligatorisch, die exakte Zeichenfolge zu verwenden, die in der obigen BNF-Grammatik angegeben ist: Es reicht aus, wenn die verwendete Syntax eine eindeutige Darstellung der Bäume ergibt. ZB können Sie []anstelle von ()eine zusätzliche Ebene von Klammern [[]]verwenden [], äußere Klammern sind vorhanden oder fehlen, zusätzliche Kommas oder keine Kommas, zusätzliche Leerzeichen, Klammern oder keine Klammern usw.

Alle diese sind gleichwertig:

(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

Auch eine Variation von @xnor in einem Kommentar. Da es eine Möglichkeit gibt, dies in ein verständliches Format zu übersetzen, ist dies akzeptabel.

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

Um dies verständlicher zu machen, konvertieren einige der so []zu ()mögen

[([])()]

Beginnen Sie jetzt mit

[]

Fügen Sie dann eine Binärdatei ein, die zwei Ausdrücke benötigt, die Sie erhalten

 [()()] which is 2

und dann füge für first () einen Unary ein, der einen Ausdruck benötigt, den du bekommst

 [([])()] which is 21

aber da []oder ()ohne innere Klammer 0 darstellen kann, was keine weiteren Ausdrücke erfordert, können Sie es als interpretieren

Beachten Sie, dass Antworten theoretisch mit unbegrenztem Speicher funktionieren sollten, bei einer implementierungsabhängigen endlichen Eingabe jedoch offensichtlich nicht genügend Speicher vorhanden ist.

Variationen der Ausgabe

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)

Ein möglicher Ort, um nach doppelten Bäumen zu suchen

Ein Ort, um nach einem Duplikat zu suchen, ist mit M (5).
Dieser eine Baum wurde zweimal für M (5) aus M (4) Bäumen generiert

(2 (1 0) (1 0))

die erste durch Hinzufügen eines unären Zweigs zu

(2 (1 0) 0)

und zweitens durch Hinzufügen eines unären Zweigs zu

(2 0 (1 0))

BNF verstehen

BNF besteht aus einfachen Regeln:

<symbol> ::= expression

wo auf der linken Seite ist ein Symbolname umgeben von <>.
Rechts ist der Ausdruck für die Konstruktion des Symbols. Einige Regeln verwenden andere Regeln in der Konstruktion, z

<e> ::= <terminal>

e kann sein a terminal

und einige Regeln haben Zeichen, die bei der Konstruktion des Symbols verwendet werden, z

<terminal> ::= "0"

terminal ist nur das Zeichen Null.

Einige Regeln können auf mehrere Arten erstellt werden, z

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

An ekann a <terminal>oder a <unary>oder a sein <binary>.

Und einige Regeln sind eine Folge von Teilen, z

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

A unarysind die Zeichen, denen (1folgt, wofür konstruiert werden kann, egefolgt von ).

Sie beginnen immer mit der Startregel, die dafür gilt <e>.

Einige einfache Beispiele:

Die einfachste Folge ist gerade 0. Wir beginnen also mit der Startregel <e>und stellen fest, dass es drei Möglichkeiten gibt:

  <terminal>   
| <unary>
| <binary>

also nimm den ersten <terminal>. Jetzt hat ein Terminal keine Auswahl mehr und ist 0. So ersetzen Sie <terminal>mit 0in der <e>Regel und Sie sind fertig.

Dann ist der nächste (1 0). Beginnen Sie mit <e>und verwenden Sie die Regel, <unary>die hat

"(1" <e> ")"

Nun, das braucht eine, <e>also kehren wir zurück <e>und treffen eine Wahl von einer der drei, diesmal eine Wahl, <terminal>die gibt 0. Ersetzen 0in (1 <e> )gibt (1 0), und dies wird ersetzt in <unary>so <e>ist (1 0).

code-golf graph-theory binary-tree Guy Coder
quelle

Also ein binärer Baum? "ein binärer Baum ist eine

Baumdatenstruktur,

3

Ihre Beschreibung ist die eines Binärbaums. Binäre Bäume müssen keine 2 Kinder haben. Es bedeutet nur, dass sie höchstens 2 Kinder haben. Ich denke, unary-binary ist nur ein spezifischerer Begriff, der eigentlich nichts anderes bedeutet.

14.

Überlegen Sie, was "BNF" für diejenigen von uns ist, die keine Informatiker sind

Luis Mendo

1

@GuyCoder Mein Punkt ist, wenn jemand "BNF" sieht und nicht weiß, was das bedeutet, dass er möglicherweise abschreckt und aufhört zu lesen. Vielleicht genügt es, den Namen anstelle des Akronyms zu verwenden und einen Link zur Wikipedia hinzuzufügen

Luis Mendo

4

@ mbomb007 Name geändert. Dafür sollte ich einen Peer-Pressure-Award bekommen. :)

Guy Coder

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]

Endknoten werden durch 0unäre bzw. binäre Knoten dargestellt (e). (ee), so sind die beiden Drei-Knoten-Bäume als (00)und gegeben ((0)).

Beispiele:

*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
quelle

5

CJam (37 Bytes)

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

Online-Demo . Beachten Sie, dass dies nicht sehr effizient ist und Sie wahrscheinlich nicht versuchen möchten, die Eingabe 5online zu berechnen .

Dissektion folgt.

Peter Taylor
quelle

5

Pyth ( 24 21 19 Bytes)

Dies basiert auf meiner Python 3-Lösung .

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

Es ist mein erstes Mal, dass ich Pyth benutze, also ist dies wahrscheinlich immer noch golffähig.

Beispiel , Ausgabe bei Eingabe ist 4:

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

1 repräsentiert einen binären Knoten, 0 repräsentiert einen unären Knoten und -1 repräsentiert einen Endknoten. Am Ende jedes Baums befindet sich ein impliziter Endknoten.

Erklärung :

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
quelle

Von Interesse: Pyth-Quellcode

Guy Coder

4

Brainfuck, 107 Bytes

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

Formatiert:

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

Probieren Sie es online aus

Die Eingabe wird als Byte genommen , und der Baum 12100wird wie folgt dargestellt \x01\x02\x03\x02: Zurückkonvertieren, Übersetzen tr/\x01\x02\x03/012/, Umkehren der Zeichenfolge und Hinzufügen eines Finales 0. Bäume werden durch getrennt \xfe. (Die Ausgabe kann leichter lesbar gemacht werden, indem z. B. das erste -in -36und das .in geändert werden +47.-47, wobei -36dies eine Zeichenfolge mit 36 -Zeichen usw. bedeutet.)

Dieser Ansatz nutzt die Eigenschaft (die auch Ben Frankel verwendet hat): Unter Berücksichtigung der möglichen Knoten als -1, 0, 1und ohne Berücksichtigung des -1Endknotens stellt eine Liste einen gültigen Baum dar, wenn und nur wenn (1) alle Präfixe der Liste eine nicht negative Summe haben, und (2) die Summe der gesamten Liste ist gleich 0. Die erste Bedingung wird beim Generieren von Zwischenknoten beibehalten, sodass am Ende nur die zweite Bedingung überprüft werden muss.

Das Band ist in 5-Knoten-Zellen unterteilt.

i d x 0 0

wo iist der Index (absteigend von links nach rechts), dist die Teilsumme und xist das Element.

Skizze des Kontrollflusses:

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)

Beachten Sie, dass ein Wert manchmal als einer oder zwei Werte größer als der tatsächliche (konzeptionelle) Wert gespeichert oder initialisiert und nach Bedarf angepasst wird.

Mitch Schwartz
quelle

3

Python 3 ( 138 134 128 121 119 Byte)

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

Beispielausgabe für 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äsentiert einen binären Knoten, 0 repräsentiert einen unären Knoten und -1 repräsentiert einen Endknoten. Am Ende jedes Baums befindet sich ein impliziter Endknoten.

Das Programm beginnt zu lange zu dauern n=17.

Ben Frankel
quelle

3

JavaScript (Firefox 30-57), 79 Byte

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

Dabei steht es -1für ein Terminal, 0einen unären Knoten und 1einen binären Knoten. Fängt an, m=14auf meinem PC langsam zu werden . Arbeitet rekursiv vom Ende des Baums zurück.

Die Anzahl der nicht berücksichtigten Knoten lwird durch die Tatsache begrenzt, dass am Ende möglicherweise nur noch 1 Knoten übrig ist.
Der Typ des nächsten Knotens nwird durch die Notwendigkeit begrenzt, dass genügend nicht berücksichtigte Knoten vorhanden sein müssen, um seine untergeordneten Knoten zu sein.

Neil
quelle

2

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

Und um die Lösungen zu zählen

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
quelle

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

Dies stellt Bäume als verschachtelte Tupel dar, z. B. ((((),), ()),), die ((())())durch Entfernen von Kommas, Leerzeichen und dem äußersten Rand umgewandelt werden können ().

Eine frühere 76-Byte-Version:

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