Variante de modélisation pour un arbre non ordonné

🧓 Cet exercice utilise une modélisation d'arbre non ordonné, avec la liste des parents.

Une bijection sur les premiers entiers

Si on mélange la liste des entiers inférieurs à \(n\), on peut obtenir une bijection. Par exemple

🐍 Script Python

# Indices    0  1  2  3  4  5
bijection = [4, 5, 0, 3, 1, 2]

Une bijection, c'est une fonction, ici :

• \(0 \mapsto 4\)
• \(1 \mapsto 5\)
• \(2 \mapsto 0\)
• \(3 \mapsto 3\)
• \(4 \mapsto 1\)
• \(5 \mapsto 2\)

Et sa fonction réciproque

• \(0 \mapsto 2\)
• \(1 \mapsto 4\)
• \(2 \mapsto 5\)
• \(3 \mapsto 3\)
• \(4 \mapsto 0\)
• \(5 \mapsto 1\)

Exemple d'arbre non ordonné

On utilise cet exemple de bijection :

🐍 Script Python

# Indices    0  1  2  3  4  5
bijection = [4, 5, 0, 3, 1, 2]

InitialementEn appliquant la bijection

graph TB
    R3("Ga") --> P1("Zo")
    R3    --> P2("Bu")
    R3    --> P3("Zo")
    P2   --> P4("Meu")
    P2   --> P5("Meu")

    S3("0") --> Q1("1")
    S3    --> Q2("2")
    S3    --> Q3("3")
    Q2   --> Q4("4")
    Q2   --> Q5("5")

🐍 Script Python

# Indices     0  1  2  3  4  5
parents = [None, 0, 0, 0, 2, 2]
assoc = {0: "Ga", 1: "Zo", 2: "Bu", 3: "Zo", 4: "Meu", 5: "Meu"}

graph TB
    R3("Ga") --> P1("Zo")
    R3    --> P2("Bu")
    R3    --> P3("Zo")
    P2   --> P4("Meu")
    P2   --> P5("Meu")

    S3("4") --> Q1("5")
    S3    --> Q2("0")
    S3    --> Q3("3")
    Q2   --> Q4("1")
    Q2   --> Q5("2")

🐍 Script Python

# Indices  0  1  2  3    4   5
parents = [4, 0, 0, 4, None, 4],
assoc = {0: "Bu", 1: "Meu", 2: "Meu", 3: "Zo", 4: "Ga", 5: "Zo"}

Explications

1. Dans la première modélisation 0 est la racine et son étiquette est "Ga".
   • Avec la bijection (\(0\mapsto 4\)), c'est 4 qui devient la racine avec l'étiquette "Ga".
2. Dans la première modélisation, 1 (dont l'étiquette est "Zo") a pour parent 0.
   • Avec la bijection (\(1\mapsto 5\) et \(0\mapsto 4\)), c'est 5 qui porte l'étiquette "Zo" et qui a 4 pour parent.
3. Etc.

Exercice

Coder une fonction variante qui prend en paramètres

• la liste des parents (modélisant un arbre non ordonné)
• le dictionnaire assoc d'association des étiquettes de l'arbre
• une bijection donnée par une liste mélangée des entiers positifs inférieurs à la taille de l'arbre (0 est un nombre positif).

et qui renvoie une nouvelle modélisation de l'arbre valide en accord avec la bijection.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)

Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)

Entrer ou sortir du mode "plein écran"
(Esc)

Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)

Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier

Exécuter le code
(Ctrl+S)Valider
Ctrl+Enter
(Clic droit pour l'historique)TéléchargerTéléverserRéinitialiser l'éditeurSauvegarder dans le navigateur

Évaluations restantes : ∞/∞

.128077.128013/.r;nbylaeu)d63m(P+02è-@U],59fq78 N_o=pcwgv41kRéhtsSCj[i:050o0l0Z0k0)0j0!0J0P0j0k0!0!0N010Z0)0O010406050!0m0r0r0k0e0i040#0M0j0m0~0M0g0J020k0r0O0f0J0W0l180e0G0m0l0!050c1517191b130O04051G1z1J0c1G130o0)0S0?0^0`0|0Y0)0R0Y0j1X0Y0Z11050.0h0j0l1S0_0{011W1Y1!1Y0Z1*1,1(0Z0e1H0Z0Y1.1U010F0:0l0g1m0l010?1e0!0O0k0g0|0w1(2e2g221:251,280r2a040b0J0t0e0M0O0M0!0)1h1j0,2c0e0e0l0P2E1z2l0g1H0c202Q1}1 1~1)0o2n0|1!0g272B1(1P1R0@1/2!0)2$0g0M2*1(0O2J1H2O2Q2{142f1j2,232;0e180j110J0U2N2 122~2m311:3335370w3a2g3c2O2Z013h0k36040J0q3l2P133o3f0|3r3t0J0T3x3n2 3p3D370D3H3z3J3B3q0M343s370p3O3d301T3g3T3i3u0H3Y3A3#3C3%3V3u0I3+3Q3-3S3U3E0E3?3e3^3L040U0v3}3!2-3_3(0U391A3b3P3~46400U3k4b3m4d45323/3t0U3w4j3y3Z3K4o110U3G4s2Q2^0l2Q2*2T0o1 2Y3R0P2=2t0+1Q1H4C2`3b3H054L0,4S4e230V110,0F4U3,460Q374)3@4f0F110S190)2g0Z0l4.4Z1:10040s4|4m3g112f2J0g0Z1y4A4u3R4 0C3H0J5c3 111/0M0P523p5e5g5i4f110h0)0%2K2M5b4*234 0n0*3O0J5H5h5B1:0!2j04011r0g0S0M0)1-0m2$0J0r2=0X1!0!0k2E0J0X1v1Q3s274`0J2G0j00190h2J015G5I5s32110.0:1,5r5K0|0M110N644/320h112q5o5d11515A6b5404565/5a2}65015D5|5H5~6m6o580!0L0S4i2{5J6l66686a4}0|4 0(6g3^0V0P110K1i4{4A6G6L014#040F3T6K533C110L6)3p0M4,042/6.3R0g6d040e2g0R6W6r6H6t6i6P5t04610j636k6Z5D0B6v6Y6*6!116%0e6@5j6=7l466:116?6X6x3C6`6|0g6~745C737a7g0g600/786 4T6s5D5F4A065I7Q7f3K550L0)7o236704697t6s7F6n196p7A4~116O7D7T7n7:6h047d7O7R5}6s6#0)4(7$717(0O7V7X1:7q6=6q3b7S3R882;0Z860|6R6T6V7,6M117N2{7P7{7R7u3q557*6A6C6E7K716N8m8v045v5x2L0)1i8E8D7?7m7W8O464 0B7_6F8u7Z7#8W7%5u5w5y8K0g8M7.8E83858R7B7^3O8r6w8#045l0P8z8h018Y8~6_4$0)2L8+500n7e8u6#7j917r8~887s8!827w6}7J3m8u4 6j706Z7(77799r7g7M7e7Q8u7(8{8}8:7-047/9w7;8H8(8L9F8n9H8-9e9O727^8V8b8X6J819s5k0`5m969I8B9#7=9J7@9W4k8@8c6Q112J0Z0m0e8*9!7E8w57599E9.3^5q9~7;9D6D3Y0c4W4D1K2_1z4F1z0Z4Haj2W2R0k1+ae0c4F1F4Y7g2J0r0L0F0k0V0l0L0Y0q111r1t1v1x0J8p4T1M3c2*3p0k0o5Z0g2D8)0J8f2t1FaSaU1iaX1i0y0~0Z1{040A0~5$5(aY0F1g9{6W1N1I1H0)0r0R0J3s0Z0|0a2b3R0Z0Q1s0M0%0)2b0!0e0P1V1_0O0!0*0cac0o0g0d0%0!0,1!0S0e0d2$0Z0c1Y0c0%0,0PaC0o2Rbb5Zbe0z0U0D0d0U0d0v0c1/0-0!1A0S0R0c0U0F0T0T0o0d0!b#2ba-1,0|0*0u0U0*010c3u0$0-5:6%0g8J1i0J0!0l6|0J1}0x0=1g260J2A9{0J0M0h4`aW0e0J5W1-5Z0o5#0)5%5)ca0=1P0F0F0Xa11-0o00cpcfax0)0x2J0J27coa=cu4_1KaQ1Q3p1=1Z1#1%av3p2p2729112v0#0P0e0 0Z2w0i209N2}4R3Z2|4Tadc#3R0V7(b02A0e8g9T6;5h9T0g7(7x0o0M0r8?9B8$8I5z9i6Z90a76^6`5$d5a48S7Cdt6c9^9l969q9+9 767H9vdC5p110n987Odh6{2gdddf9T7Z0d9R040!0Y0mcAdG9n7LdvdH6^di9M9}dw9GdL8q4ldI9QdS110dd`969:4t8_6za2aa9Ta6dldDa98A3m9?7p9Ze57;4?c.4_9m2P9od(d$82a07+e3115fdo7m8{96esedd*8G8%c3d-d)a5dJabc}afaratah4P13as0-7H0!04.