Ein Baum ist ein verbundener, ungerichteter Graph ohne Zyklen. Ihre Aufgabe ist es zu zählen, wie viele verschiedene Bäume es mit einer bestimmten Anzahl von Eckpunkten gibt.

Zwei Bäume gelten als verschieden, wenn sie nicht isomorph sind . Zwei Diagramme sind isomorph, wenn ihre jeweiligen Scheitelpunkte so gepaart werden können, dass genau dann eine Kante zwischen zwei Scheitelpunkten in einem Diagramm liegt, wenn zwischen den Scheitelpunkten, die mit diesen Scheitelpunkten im anderen Diagramm gepaart sind, eine Kante vorhanden ist. Eine ausführlichere Beschreibung finden Sie unter dem obigen Link.

Schauen Sie hier , um zu sehen, wie alle unterschiedlichen Bäume der Größen 1 bis 6 aussehen .

Die Serie, die Sie ausgeben möchten, ist A000055 bei der OEIS.

Einschränkung : Die Ausführung Ihrer Lösung muss maximal Minuten dauern 6. Dies soll nicht exponentielle Zeitalgorithmen eliminieren, aber es soll doppelt exponentielle Zeitalgorithmen eliminieren, wie z. B. Brute Forcing über alle Kantenmengen.

Eingabe: Beliebige nicht negative Ganzzahl.

Die Eingabe kann mit jedem Standardmittel erfolgen, einschließlich STDIN, Befehlszeilenparameter, Funktionseingabe usw.

Ausgabe: Die Anzahl der unterschiedlichen Bäume mit so vielen Scheitelpunkten wie die Eingabe.

Die Ausgabe kann mit allen Standardmitteln erfolgen, einschließlich STDOUT, Funktionsrückgabe usw.

Beispiele: 0, 1, 2, 3, 4, 5, 6, 7 sollte zurückkehren 1, 1, 1, 1, 2, 3, 6, 11.

Wertung: Code Golf, in Bytes. Möge der kürzeste Code gewinnen!

Standardlücken verboten.

CJam (69 Bytes)

]qi:X,{1e|,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/z

Online-Demo

Erläuterung

$0$$-1$$z$

.*:+{.*:+}:F~$0$

---

Wir verwenden die Hilfsgenerierungsfunktion für A000081 , deren Begriffe die Wiederholung haben

a[0] = 0
a[1] = 1
For n >= 1, a[n+1] = (sum_{k=1}^n a[n-k+1] * sum_{d|k} d * a[d]) / n

$\sum_{d\mid k} d \times a[d]$$d$k % d == 0 ? d : 0$a$.*$a$$k$$a$$n$N\f{1$%!*}W$.*:+

M

$$a[n+1] = \frac{1}{n} \sum_{k=1}^n a[n-k+1] \times M[k]$$

$a$$M$$1$$n$$n + 1$$a$

 qi:X,{   ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/

Der Punkt der Hilfsgenerierungsfunktion wird durch den Formelabschnitt von A000055 angegeben:

G.f.: A(x) = 1 + T(x) - T^2(x)/2 + T(x^2)/2,
where T(x) = x + x^2 + 2*x^3 + ... is the g.f. for A000081.

$a$

$$[x = 0] + a[x] + \frac{1}{2}\left(a[x/2] - \sum_{i=0}^n a[i] \times a[n-i]\right)$$

$a[x/2]$$x$1,*X=

0\+$a[0] = 0$$X = 0$W\+$-2a[x] + \sum_{i=0}^n a[i] \times a[n-i]$$2$$a[x]$

Also haben wir erklärt

 qi:X,{   ,:):N{N\f{1$%!*}W$.*:+}%1$W%.*:+N,/+}/W\+_1,*X=\_W%.*:+-Y/

Die übrigen Angaben beziehen sich auf den Sonderfall. Ich habe die Wiederholung ursprünglich strenger verfolgt, indem ich mit1] und von iteriert habe$N = 1$

1]qi:X,1>{ ... }/

$X = 0$$a$[-1 1]$0$$[x = 0]$X!+1e|

$a$$1$$N = 0$

]qi:X,{ ... /+}/

gibt offensichtlich Division durch Null. Aber wenn wir es versuchen

]qi:X,{1e| ... /+}/

dann funktioniert es. Wir bekommen

             e# Stack: [] 0
1e|          e# Stack: [] 1
,:):N        e# Stack: [] [1]
{            e# We only execute this loop once
  N\f{1$%!*} e#   1 divides 1, so stack: [] [1]
  W$.*       e#   Remember: if the two arrays supplied to the pointwise operation
             e#   are not the same length then the values from the longer one are
             e#   left untouched. Stack: [] [1]
  :+         e#   Fold over a singleton. Stack: [] 1
}%           e# And that was a map, so stack: [] [1]
1$W%.*:+     e# Another [1] [] .*:+, giving the same result: 1
N,/          e# 1 / 1 = 1
+            e# And we append 1 to a giving [1]

Das ergibt genau den Wert, den wir benötigen.

$X = 0$$-1$[-1]$(-1 - \frac12(-1 \times -1)) = -1$$0$$1$$-1$$1$z

Pyth, 35 Bytes

l{m`SmSSMcXdUQk2.pQusm+L,dhHGhHtQ]Y

Demonstration.

Dieses Programm kann in zwei Teile unterteilt werden: Zuerst generieren wir alle möglichen Bäume, dann entfernen wir Duplikate.

Dieser Code generiert die Bäume : usm+L,dhHGhHtQ]Y. Bäume werden wie folgt als verkettete Liste von Kanten dargestellt:

[0, 1, 0, 2, 2, 3, 1, 4]

Jede Zahl steht für einen Scheitelpunkt und jede zweite Zahl ist eine Kante. Es wird erstellt, indem wiederholt eine Kante zwischen jedem möglichen bereits vorhandenen und einem neu erstellten Scheitelpunkt hinzugefügt wird und diese jedem möglichen Baum aus dem vorherigen Schritt hinzugefügt wird. Dies generiert alle möglichen Bäume, da alle Bäume durch wiederholtes Hinzufügen eines Scheitelpunkts und einer Kante davon zum vorhandenen Baum generiert werden können. Es werden jedoch isomorphe Bäume erstellt.

Als nächstes führen wir für jeden Baum jede mögliche Neukennzeichnung durch. Dazu werden alle möglichen Permutationen der Eckpunkte ( m ... .pQ) abgebildet und anschließend der Baum von der Standardreihenfolge in diese Reihenfolge mit übertragen XdUQk. dist der Baum, kist die Permutation.

Dann trennen wir die Kanten in separate Listen mit c ... 2, sortieren die Eckpunkte innerhalb jeder Kante mit SM, sortieren die Kanten innerhalb des Baums mit Sund geben eine kanonische Darstellung jedes Baums. Diese beiden Schritte sind der Code mSSMcXdUQk2.pQ.

Jetzt haben wir eine Liste von Listen, die sich aus jeder möglichen Umbenennung jedes Baums zusammensetzt. Wir sortieren diese Listen mit S. Zwei beliebige isomorphe Bäume müssen in die Baumgruppe eingeteilt werden können. Mit dieser Tatsache konvertieren wir jede Liste in eine Zeichenfolge mit `, bilden dann die Menge dieser Listen mit {und geben ihre Länge mit aus l.