Graf Eulers Touren
Leonhard Euler möchte ein paar Freunde besuchen, die in den Häusern 2, 3, ..., N leben (er wohnt in Haus 1). Aufgrund der Gestaltung seiner Stadt bildet jedoch keiner der Pfade zwischen den Häusern eine Schleife (die Häuser befinden sich also in einer Grafik, die ein Baum ist).
Er langweilt sich leicht, aber wenn er seine Freunde in einer anderen Reihenfolge besucht, wird er sich nicht langweilen. Er möchte, dass Sie ihm helfen, herauszufinden, wie viele einzigartige Möglichkeiten es für ihn gibt, jeden Freund zu besuchen und am Ende des Tages nach Hause zurückzukehren.
Er hat keine Karte seiner Stadt, aber er erinnert sich an die Reihenfolge der Häuser, die er das letzte Mal besucht hat, als er spazieren ging.
Problemstellung
Bestimmen Sie anhand der Euler-Tour-Darstellung eines Baums die Anzahl der eindeutigen ETRs desselben Baums, wobei die Wurzel bei 1 liegt.
Eingang
Die ETR eines Baumes. Die Euler-Tour-Darstellung beginnt im Wesentlichen an der Wurzel und durchquert die Baumtiefe. Schreiben Sie zuerst die Beschriftung jedes Knotens aus. Ein 3-Knoten-Baum mit einer Wurzel und zwei untergeordneten Elementen würde als dargestellt 1 -> 2 -> 1 -> 3 -> 1. Ein 3-Knoten-Baum mit einer Wurzel, einem Kind und einem Enkelkind würde als dargestellt 1 -> 2 -> 3 -> 2 -> 1.
Mit anderen Worten, es stellt die Eulersche Schaltung eines gerichteten Graphen dar, der aus der Erzeugung von zwei Kanten von jeder Kante im Baum abgeleitet ist, eine in jeder Richtung.
Hier ist ein visuelles Beispiel für eine ETR:
Ich werde einige Änderungen an der Eingabe zulassen:
- Sie können wählen, ob Blattknoten ein- oder zweimal hintereinander geschrieben werden sollen.
- Sie können wählen, ob Sie am Ende zum Stamm zurückkehren möchten.
Hier ist zum Beispiel ein Baum:
1
/ \
2 3
/ \ \
4 5 6
Folgendes ist akzeptabel:
1 2 4 2 5 2 1 3 6 3 11 2 4 2 5 2 1 3 6 31 2 4 4 2 5 5 2 1 3 6 6 3 11 2 4 4 2 5 5 2 1 3 6 6 3(Dies wird im Wikipedia-Artikel gezeigt)
Sie können die Eingabe in einem beliebigen vernünftigen Format für eine Liste von Ganzzahlen vornehmen. Sie können auch zuerst die Eingabe N(die Anzahl der Knoten) und die Indizierung bei einem beliebigen Wert anfordern (ich verwende hier die 1-Indizierung). Ihre Knotenbezeichnungen xmüssen jedoch ab sein x, x+1, x+2, ..., x+N-1.
Ausgabe
Eine Ganzzahl, die die Anzahl der eindeutigen ETRs dieses Baums darstellt, beginnend mit demselben Stammknoten.
Herausforderungsspezifikationen und -regeln
- Beachten Sie, dass Eingaben NICHT immer Binärbäume sind. siehe den zweiten Testfall
- Dies ist ein Code-Golf- Problem, daher erfolgt die Bewertung nach Codelänge, wobei eine niedrigere Punktzahl besser ist
- Es wird keine Antwort akzeptiert
- Es gelten Standardlücken
Testfälle
[1, 2, 3, 2, 4, 5, 4, 6, 4, 2, 1, 7, 8, 9, 8, 7, 1] -> 8
[1, 2, 3, 2, 4, 2, 1, 5, 6, 5, 7, 5, 1, 8, 9, 8, 10, 8, 1] -> 48
[1, 2, 3, 4, 5, 6, 7, 6, 8, 6, 5, 9, 5, 4, 10, 4, 3, 11, 3, 2, 12, 2, 1] -> 32
[1] -> 1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1] -> 1
Wenn Sie mit mehr Daten testen möchten, finden Sie hier meine Referenzimplementierung . Es ist ziemlich schlecht, aber es ist richtig, so dass Sie es verwenden können; Ändern Sie einfach die Liste in Zeile 3.
Antworten
Python 2 , 45 Bytes
f=lambda l:l==[]or(l.count(l.pop())or 1)*f(l)
Probieren Sie es online aus!
Es scheint, dass eine Möglichkeit, die Antwort zu erhalten, darin besteht, die Anzahl der einzelnen Knoten zu ermitteln, dh die Häufigkeit, mit der jeder Knoten aufgelistet wird, 1 von jedem zu subtrahieren und ihre Fakultäten zu multiplizieren. Das ist,
$$\prod_i (c_i-1)!$$
wo Knoten \$i\$ist aufgeführt \$c_i\$mal. Beachten Sie, dass es keine Rolle spielt, in welcher Reihenfolge die Knoten in der Euler-Tour-Darstellung angezeigt werden, sondern nur, wie oft sie angezeigt werden. Das ein- oder zweimalige Auflisten von Blattknoten macht keinen Unterschied, da \$0!=1!=1\$.
Da Python keine eingebaute Fakultät hat, machen wir das so. Für jeden Eintrag in der Liste wird gezählt, wie oft dieselben Werte vor der Liste angezeigt werden, dh, wie sie kals 0-indiziert angezeigt wird k. Zum Beispiel,
1 2 4 2 5 2 1 3 6 3 1
0 0 0 1 0 2 1 0 0 1 2
Wenn wir dann alle Nullen entfernen (oder in Einsen umwandeln) und multiplizieren, erhalten wir das gewünschte Ergebnis.
Um dies rekursiv zu tun, entfernen wir wiederholt das letzte Element und betrachten seine Anzahl im Rest der Liste, wobei wir eine beliebige Anzahl von 0 in 1 konvertieren. Dann multiplizieren wir mit dem rekursiven Ergebnis in der Liste, wobei das letzte Element jetzt entfernt wird, mit ein Basisfall von 1 für die leere Liste.
Wir können ein paar Bytes mit Splatted Input und Truefür 1 speichern, wenn dies erlaubt ist.
43 Bytes
f=lambda a,*l:l==()or(l.count(a)or 1)*f(*l)
Probieren Sie es online aus!
APL (Dyalog Unicode) , 17 11 Bytes
Basierend auf der Antwort von xnor . Der ⍤Bediener benötigt Version 18, die noch nicht auf TIO verfügbar ist.
(×/!÷⊢)≢⍤⊢⌸
Hier ist eine längere Variante, die in niedrigeren Versionen funktioniert:
(×/!÷⊢)∘(+/∪∘.=⊢)
Probieren Sie es online aus!
+/∪∘.=⊢/ ≢⍤⊢⌸zählt das Vorkommen der eindeutigen Elemente in der Eingabe, ×/!÷⊢berechnet$$\prod_i{c_i!\over c_i}$$
APL (Dyalog Unicode) , 27 Bytes
Ich denke, das funktioniert mit allen vorgeschlagenen Eingabeformaten.
{2>≢⍵:1⋄(×/∇¨,∘!≢)⍵⊆⍨⍵≠⌊/⍵}
Probieren Sie es online aus!
Ich denke nicht, dass der Basisfall 2>≢⍵:1wirklich notwendig ist, da es irgendwann keine Teilbäume mehr gibt, auf die man zurückgreifen kann, aber ich kann dies nicht ohne ihn zum Laufen bringen.
Kommentiert:
{2>≢⍵:1⋄(×/∇¨,∘!≢)⍵⊆⍨⍵≠⌊/⍵} ⍝ A recursive dfns
2>≢⍵ ⍝ If the input has less than 2 elements
:1 ⍝ return 1
⍵⊆⍨ ⍝ Partition the input ...
⍵≠ ⍝ ... taking the elements that are not equal
⌊/⍵ ⍝ to the minimum (the root of the current tree)
⍝ These are the new subtrees
!≢ ⍝ Take the factorial of the number of subtrees
, ⍝ And append it to the results of ...
∇¨ ⍝ the recursive calls on each subtree
×/ ⍝ take the product of the vector
⍝ this is the result
Gelee , 5 Bytes
ĠẈ’!P
Probieren Sie es online aus!
Count Eulers Tours 5-Byte-Gelee-Lösung, wie von HyperNeutrino erwähnt .
Die Idee ist die gleiche wie bei einer früheren Python-Lösung, aber ich möchte trotzdem erklären, wie ich dazu gekommen bin.
Beachten Sie, dass wir dies rekursiv lösen können. Wenn unser aktueller Knoten N mit C Kindern ist, lautet unsere Antwort C! mal das Produkt der Unterantworten aller Kinder. Der Grund ist, dass wir (in unserer Euler-Tour) in beliebiger Reihenfolge in die Kinder hinabsteigen können.
Die zweite Beobachtung ist, dass für jeden Knoten außer der Wurzel, wobei count (x) die Anzahl der Vorkommen von x in der Eulertour ist:
$$count(i) = deg(i)$$
Für die Wurzel
$$count(r) = deg(r) + 1$$
Wenn wir uns nun unsere Formel oben ansehen, stellen wir fest, dass unsere Antwort lautet
$$deg(r)! * [deg(n) - 1]!$$
für jeden anderen Knoten n. Das klappt eigentlich komisch gut. Wir stellen fest, dass die Antwort, wie bereits erwähnt, lautet:
$$\prod_{i = 1}^v [count(v) - 1]!$$
Diese Lösung eignet sich sehr gut für Gelee.
ĠẈ’!P
Zuerst erhalten wir das Count-Array, das wir benötigen, indem Ġwir die Indizes nach ihren Elementen gruppieren und die vektorisierte Länge nehmen. Dann dekrementieren und faktoriell und schließlich Produkt:
ĠẈ Count array
’ Decrement
! Factorial
P Product
PS: Vielen Dank an HyperNeutrino, der mir bei der Geleelösung geholfen hat, da mein Gelee etwas rostig ist ...
JavaScript (ES6), 42 Byte
Dies basiert auf der Vermutung von @ xnor .
a=>a.map(x=>t*=(a[~x]=-~a[~x])-1||1,t=1)|t
Probieren Sie es online aus!
Holzkohle , 11 Bytes
ＩΠＥθ∨№…θκι¹
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Verwendet den Algorithmus von @ xnor. Erläuterung:
θ Input array
Ｅ Map over elements
θ Input array
… Truncated to length
κ Current index
№ Count occurrences of
ι Current element
∨ Logical Or
¹ Literal `1`
Π Take the product
Ｉ Cast to string
Implicitly print
Unter Verwendung der Darstellungsform, bei der Blattknoten einmal besucht werden und der Wurzelknoten eine zusätzliche Kante aufweist, so dass er sowohl am Anfang als auch am Ende besucht wird, entspricht die Anzahl der Kanten für einen bestimmten Knoten der Anzahl von Mal wurde es besucht. Beim ersten Besuch eines Knotens mit nKanten haben Sie nur eine Auswahl an n-1Kanten, da Sie alle Teilbäume vollständig durchlaufen müssen, bevor Sie zum übergeordneten Knoten zurückkehren. Bei nachfolgenden Besuchen haben Sie weniger Auswahlmöglichkeiten, bis Sie schließlich die letzten beiden Besuche erhalten überhaupt keine Wahl. Dies könnte auf die Produkte der relevanten Fakultäten für jeden Knoten reduziert werden, obwohl es, wie @xnor betont, für einige Sprachen tatsächlich schwieriger ist, jeden Besuch durch die Anzahl der verbleibenden Auswahlmöglichkeiten zu ersetzen und das Gesamtprodukt zu übernehmen (der Charcoal-Algorithmus übernimmt tatsächlich das Produkt in umgekehrter Reihenfolge, aber dies macht natürlich keinen Unterschied zur Gesamtsumme).
05AB1E , 5 Bytes
Ù¢<!P
Ein bisschen lahm, aber dies ist einfach eine Portierung von @xnors Python 2-Antwort und @ Riolkus Jelly-Antwort , also stellen Sie sicher, dass Sie sie positiv bewerten!
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
Ù # Uniquify the (implicit) input-list
¢ # Count how many times each occurs in the (implicit) input-list
< # Decrease each count by 1
! # Take the factorial on each value
P # And take the product of that
# (after which it is output implicitly as result)
Perl 5 -ap , 27 Bytes
$\=1;$\*=$h{$_}++||1for@F}{
Probieren Sie es online aus!
Japt , 8 Bytes
ü ®ÅÊÊÃ×
Versuch es