introduction

Dans ce défi, votre tâche consiste à écrire un programme qui décide si deux arbres donnés sont isomorphes. Un arbre signifie un graphe acyclique dirigé où chaque nœud a exactement un bord sortant, sauf la racine, qui n'en a pas. Deux arbres sont isomorphes si l'un peut être transformé en l'autre en renommant les nœuds. Par exemple, les deux arbres (où chaque bord pointe vers le haut)

  0       0
 /|\     /|\
1 3 4   1 2 5
|\       /|
2 5     3 4

sont facilement considérés comme isomorphes.

Nous codons un arbre comme une liste Ld'entiers non négatifs de la manière suivante. La racine de l'arbre a une étiquette 0et elle a également des nœuds 1,2,...,length(L). Chaque nœud i > 0a un front sortant vers L[i](à l'aide d'une indexation basée sur 1). Par exemple, la liste (avec les indices donnés sous les éléments)

[0,0,1,3,2,2,5,0]
 1 2 3 4 5 6 7 8

code l'arbre

  0
 /|\
1 2 8
| |\
3 5 6
| |
4 7

Contribution

Vos entrées sont deux listes d'entiers non négatifs, donnés au format natif ou dans votre langue. Ils codent deux arbres de la manière indiquée ci-dessus. Vous pouvez assumer les conditions suivantes à leur sujet:

1. Ils ne sont pas vides.
2. Ils ont la même longueur.
3. Chaque liste Lsatisfait L[i] < ipour tous les indices (basés sur 1) i.

Production

Votre sortie doit être une valeur véridique si les arbres sont isomorphes et une valeur fausse si ce n'est pas le cas.

Règles et notation

Vous pouvez écrire soit un programme complet soit une fonction. Le nombre d'octets le plus bas l'emporte et les failles standard sont interdites. Il n'y a aucune restriction de temps, mais les éléments intégrés qui décident de l'isomorphisme d'arbre ou de graphique sont interdits.

Cas de test

Instances véridiques

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

Instances de fausseté

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

Mathematica, 48 octets

SameQ@@(Sort//@(0(0//.PositionIndex@#))&/@{##})&

C'est encore plus court que la solution qui utilise IsomorphicGraphQ:

IsomorphicGraphQ@@(Graph@*MapIndexed[#->Tr@#2&]/@{##})&

Python, 83

La fonction anonyme sur la 2ème ligne est ma solution.

f=lambda l,i=0:sorted(f(l,j+1)for j,e in enumerate(l)if e==i)
lambda a,b:f(a)==f(b)

frenvoie une forme canonisée d'un sous-arbre qui est une liste triée de ses enfants canonisés. Ensuite, nous devons simplement vérifier si les formes canonisées de chaque arbre sont égales.