Einführung
In dieser Herausforderung besteht Ihre Aufgabe darin, ein Programm zu schreiben, das entscheidet, ob zwei gegebene Bäume isomorph sind. Ein Baum ist ein gerichteter azyklischer Graph, bei dem jeder Knoten genau eine ausgehende Kante hat, mit Ausnahme der Wurzel, die keine hat. Zwei Bäume sind isomorph, wenn einer durch Umbenennen der Knoten in den anderen umgewandelt werden kann. Zum Beispiel die beiden Bäume (wo jede Kante nach oben zeigt)
0 0
/|\ /|\
1 3 4 1 2 5
|\ /|
2 5 3 4
sind leicht zu sehen, isomorph zu sein.
Wir kodieren einen Baum wie L
folgt als Liste nichtnegativer Ganzzahlen. Die Wurzel des Baums hat eine Bezeichnung 0
und Knoten 1,2,...,length(L)
. Jeder Knoten i > 0
hat eine ausgehende Flanke zu L[i]
(unter Verwendung einer 1-basierten Indizierung). Zum Beispiel die Liste (mit den unter den Elementen angegebenen Indizes)
[0,0,1,3,2,2,5,0]
1 2 3 4 5 6 7 8
kodiert den Baum
0
/|\
1 2 8
| |\
3 5 6
| |
4 7
Eingang
Ihre Eingaben bestehen aus zwei Listen nichtnegativer Ganzzahlen, die im systemeigenen Format oder in Ihrer Sprache angegeben sind. Sie codieren zwei Bäume in der oben angegebenen Weise. Sie können die folgenden Bedingungen über sie annehmen:
- Sie sind nicht leer.
- Sie haben die gleiche Länge.
- Jede Liste
L
erfülltL[i] < i
alle (1-basierten) Indizesi
.
Ausgabe
Ihre Ausgabe soll ein wahrer Wert sein, wenn die Bäume isomorph sind, und ein falscher Wert, wenn nicht.
Regeln und Wertung
Sie können entweder ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Es gibt keine zeitlichen Einschränkungen, aber integrierte Funktionen, die über die Isomorphie von Bäumen oder Graphen entscheiden, sind nicht zulässig.
Testfälle
Wahrheitsinstanzen
[0] [0]
[0,1,2,1] [0,1,1,3]
[0,1,1,3,3] [0,1,2,2,1]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,4,2,1]
[0,1,2,3,1,2,3,0,8] [0,1,0,3,3,4,4,7,7]
Falsche Instanzen
[0,0] [0,1]
[0,1,2,0,3,3,4] [0,1,2,3,0,4,3]
[0,1,0,1,2,3,3,0] [0,0,2,1,0,5,2,1]
[0,1,1,0,1,3,2,1,5] [0,1,0,3,3,3,2,5,2]
[0,1,2,3,1,2,3,0,8] [0,1,0,1,4,4,5,6,6]
[0,1,0,2,0,3,0,4,0,5] [0,0,2,1,0,3,4,0,0,9]
Antworten:
Mathematica, 48 Bytes
Es ist noch kürzer als die Lösung, die verwendet
IsomorphicGraphQ
:quelle
Python, 83
Die anonyme Funktion in der 2. Zeile ist meine Lösung.
f
gibt eine kanonisierte Form eines Unterbaums zurück, die eine sortierte Liste seiner kanonisierten untergeordneten Elemente ist. Dann müssen wir einfach prüfen, ob die kanonisierten Formen der einzelnen Bäume gleich sind.quelle