<jupyter_start><jupyter_text>Table of Contents1&nbsp;&nbsp;TP 2 - Programmation pour la préparation à l'agrégation maths option info2&nbsp;&nbsp;Listes2.1&nbsp;&nbsp;Exercice 1 : taille2.2&nbsp;&nbsp;Exercice 2 : concat2.3&nbsp;&nbsp;Exercice 3 : appartient2.4&nbsp;&nbsp;Exercice 4 : miroir2.5&nbsp;&nbsp;Exercice 5 : alterne2.6&nbsp;&nbsp;Exercice 6 : nb_occurrences2.7&nbsp;&nbsp;Exercice 7 : pairs2.8&nbsp;&nbsp;Exercice 8 : range2.9&nbsp;&nbsp;Exercice 9 : premiers3&nbsp;&nbsp;Listes simplement chaînée (manuellement définies)3.1&nbsp;&nbsp;La classe ListeChainee3.2&nbsp;&nbsp;Exercice 1 : taille3.3&nbsp;&nbsp;Exercice 2 : concat3.4&nbsp;&nbsp;Exercice 3 : appartient3.5&nbsp;&nbsp;Exercice 4 : miroir3.6&nbsp;&nbsp;Exercice 5 : alterne3.7&nbsp;&nbsp;Exercice 6 : nb_occurrences3.8&nbsp;&nbsp;Exercice 7 : pairs3.9&nbsp;&nbsp;Exercice 8 : range3.10&nbsp;&nbsp;Exercice 9 : premiers4&nbsp;&nbsp;Quelques tris par comparaison4.1&nbsp;&nbsp;Exercice 10 : Tri insertion4.2&nbsp;&nbsp;Exercice 11 : Tri insertion générique4.3&nbsp;&nbsp;Exercice 12 : Tri selection4.4&nbsp;&nbsp;Exercices 13, 14, 15 : Tri fusion4.5&nbsp;&nbsp;Comparaisons5&nbsp;&nbsp;Listes : l'ordre supérieur5.1&nbsp;&nbsp;Exercice 16 : applique5.2&nbsp;&nbsp;Exercice 175.3&nbsp;&nbsp;Exercice 18 : itere5.4&nbsp;&nbsp;Exercice 195.5&nbsp;&nbsp;Exercice 20 : qqsoit et ilexiste5.6&nbsp;&nbsp;Exercice 21 : appartient version 25.7&nbsp;&nbsp;Exercice 22 : filtre5.8&nbsp;&nbsp;Exercice 235.9&nbsp;&nbsp;Exercice 24 : reduit5.10&nbsp;&nbsp;Exercice 25 : somme, produit5.11&nbsp;&nbsp;Exercice 26 : miroir version 26&nbsp;&nbsp;Arbres6.1&nbsp;&nbsp;Exercice 276.2&nbsp;&nbsp;Exercice 286.3&nbsp;&nbsp;Exercice 296.4&nbsp;&nbsp;Exercice 307&nbsp;&nbsp;Parcours d'arbres binaires7.1&nbsp;&nbsp;Exercice 317.2&nbsp;&nbsp;Exercice 32 : Parcours naifs (complexité quadratique)7.3&nbsp;&nbsp;Exercice 33 : Parcours linéaires7.4&nbsp;&nbsp;Exercice 34 : parcours en largeur et en profondeur7.5&nbsp;&nbsp;Exercice 35 et fin7.5.1&nbsp;&nbsp;Reconstruction depuis le parcours prefixe7.5.2&nbsp;&nbsp;Reconstruction depuis le parcours en largeur8&nbsp;&nbsp;Conclusion  TP 2 - Programmation pour la préparation à l'agrégation maths option info- En Python, version 3.<jupyter_code>from sys import version
print(version)<jupyter_output>3.5.3 (default, Jan 19 2017, 14:11:04) 
[GCC 6.3.0 20170118]<jupyter_text>---- ListesCes exercices sont un peu foireux : les "*listes*" en Python **ne sont pas des listes simplement chaînées** !  Exercice 1 : `taille`<jupyter_code>from typing import TypeVar, List
_a = TypeVar('alpha')

def taille(liste : List[_a]) -> int:
    longueur = 0
    for _ in liste:
        longueur += 1
    return longueur

taille([])
taille([1, 2, 3])
len([])
len([1, 2, 3])<jupyter_output><empty_output><jupyter_text>Exercice 2 : `concat`<jupyter_code>from typing import TypeVar, List
_a = TypeVar('alpha')

def concatene(liste1 : List[_a], liste2 : List[_a]) -> List[_a]:
    # return liste1 + liste2  # easy solution
    liste = []
    for i in liste1:
        liste.append(i)
    for i in liste2:
        liste.append(i)
    return liste
concatene([1, 2], [3, 4])
[1, 2] + [3, 4]<jupyter_output><empty_output><jupyter_text>Mais attention le typage est toujours optionnel en Python :<jupyter_code>concatene([1, 2], ["pas", "entier", "?"])<jupyter_output><empty_output><jupyter_text>Exercice 3 : `appartient`<jupyter_code>from typing import TypeVar, List
_a = TypeVar('alpha')

def appartient(x : _a, liste : List[_a]) -> bool:
    for y in liste:
        if x == y:
            return True  # on stoppe avant la fin
    return False

appartient(1, [])
appartient(1, [1])
appartient(1, [1, 2, 3])
appartient(4, [1, 2, 3])
1 in []
1 in [1]
1 in [1, 2, 3]
4 in [1, 2, 3]<jupyter_output><empty_output><jupyter_text>Notre implémentation est évidemment plus lente que le test `x in liste` de la librarie standard...Mais pas tant :<jupyter_code>%timeit appartient(1000, list(range(10000)))
%timeit 1000 in list(range(10000))<jupyter_output>173 µs ± 4.68 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
166 µs ± 6.56 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)<jupyter_text>Exercice 4 : `miroir`<jupyter_code>from typing import TypeVar, List
_a = TypeVar('alpha')

def miroir(liste : List[_a]) -> List[_a]:
    # return liste[::-1]  # version facile
    liste2 = []
    for x in liste:
        liste2.insert(0, x)
    return liste2
miroir([2, 3, 5, 7, 11])
[2, 3, 5, 7, 11][::-1]
%timeit miroir([2, 3, 5, 7, 11])
%timeit [2, 3, 5, 7, 11][::-1]<jupyter_output>968 ns ± 67.4 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
216 ns ± 8.77 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)<jupyter_text>Exercice 5 : `alterne` La sémantique n'était pas très claire, mais on peut imaginer quelque chose comme ça :<jupyter_code>from typing import TypeVar, List
_a = TypeVar('alpha')

def alterne(liste1 : List[_a], liste2 : List[_a]) -> List[_a]:
    liste3 = []
    i, j = 0, 0
    n, m = len(liste1), len(liste2)
    while i < n and j < m:  # encore deux
        liste3.append(liste1[i])
        i += 1
        liste3.append(liste2[j])
        j += 1
    while i < n:  # si n > m
        liste3.append(liste1[i])
        i += 1
    while j < m:  # ou si n < m
        liste3.append(liste2[j])
        j += 1
    return liste3
alterne([3, 5], [2, 4, 6])
alterne([1, 3, 5], [2, 4, 6])
alterne([1, 3, 5], [4, 6])<jupyter_output><empty_output><jupyter_text>La complexité est linéaire en $\mathcal{O}(\max(|\text{liste 1}|, |\text{liste 2}|)$.  Exercice 6 : `nb_occurrences`<jupyter_code>from typing import TypeVar, List
_a = TypeVar('alpha')

def nb_occurrences(x : _a, liste : List[_a]) -> int:
    nb = 0
    for y in liste:
        if x == y:
            nb += 1
    return nb

nb_occurrences(0, [1, 2, 3, 4])
nb_occurrences(2, [1, 2, 3, 4])
nb_occurrences(2, [1, 2, 2, 3, 2, 4])
nb_occurrences(5, [1, 2, 3, 4])<jupyter_output><empty_output><jupyter_text>Exercice 7 : `pairs`C'est un filtrage :<jupyter_code>filter?
from typing import List

def pairs(liste : List[int]) -> List[int]:
    # return list(filter(lambda x : x % 2 == 0, liste))
    return [x for x in liste if x % 2 == 0]
pairs([1, 2, 3, 4, 5, 6])
pairs([1, 2, 3, 4, 5, 6, 7, 100000])
pairs([1, 2, 3, 4, 5, 6, 7, 100000000000])
pairs([1, 2, 3, 4, 5, 6, 7, 1000000000000000000])<jupyter_output><empty_output><jupyter_text>Exercice 8 : `range`<jupyter_code>from typing import List

def myrange(n : int) -> List[int]:
    liste = []
    i = 1
    while i <= n:
        liste.append(i)
        i += 1
    return liste
myrange(4)
from typing import List

def intervale(a : int, b : int=None) -> List[int]:
    if b == None:
        a, b = 1, a
    liste = []
    i = a
    while i <= b:
        liste.append(i)
        i += 1
    return liste
intervale(10)
intervale(1, 4)<jupyter_output><empty_output><jupyter_text>Exercice 9 : `premiers`Plusieurs possibilités. Un filtre d'Erathosthène marche bien, ou une filtration.Je ne vais pas utiliser de tableaux donc on est un peu réduit d'utiliser une filtration (filtrage ? *pattern matching*)<jupyter_code>def racine(n : int) -> int:
    i = 1
    for i in range(n + 1):
        if i*i > n:
            return i - 1
    return i

racine(1)
racine(5)
racine(102)
racine(120031)
from typing import List

def intervale2(a : int, b : int, pas : int=1) -> List[int]:
    assert pas > 0
    liste = []
    i = a
    while i <= b:
        liste.append(i)
        i += pas
    return liste
intervale2(2, 12, 1)
intervale2(2, 12, 3)<jupyter_output><empty_output><jupyter_text>Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne.<jupyter_code>def estDivisible(n : int, k : int) -> bool:
    return (n % k) == 0
estDivisible(10, 2)
estDivisible(10, 3)
estDivisible(10, 4)
estDivisible(10, 5)
def estPremier(n : int) -> bool:
    return (n == 2) or (n == 3) or not any(map(lambda k: estDivisible(n, k), intervale2(2, racine(n), 1)))
for n in range(2, 20):
    print(n, list(map(lambda k: estDivisible(n, k), intervale2(2, racine(n), 1))))
from typing import List

def premiers(n : int) -> List[int]:
    return [p for p in intervale2(2, n, 1) if estPremier(p)]
premiers(10)
premiers(100)<jupyter_output><empty_output><jupyter_text>---- Listes simplement chaînée (manuellement définies)Comme ces exercices étaient un peu foireux à écrire avec les "*listes*" de Python, qui **ne sont pas des listes simplement chaînées**, je propose une autre solution où l'on va définir une petite classe qui représentera une liste simplement chaînée, et on va écrire les fonctions demandées avec cette classe.  La classe `ListeChainee`On va supposer que les listes que l'on représentera ne contiendront pas la valeur `None`, qui est utilisée pour représenter l'absence de tête et/ou de queue de la liste.<jupyter_code>class ListeChainee():
    def __init__(self, hd=None, tl=None):
        self.hd = hd
        self.tl = tl
    
    def __repr__(self) -> str:
        if self.tl is None:
            if self.hd is None:
                return "[]"
            else:
                return f"{self.hd} :: []"
        else:
            return f"{self.hd} :: {self.tl}"
    
    def jolie(self) -> str:
        if self.tl is None:
            if self.hd is None:
                return "[]"
            else:
                return f"[{self.hd}]"
        else:
            j = self.tl.jolie()
            j = j.replace("[", "").replace("]", "")
            if j == "":
                return f"[{self.hd}]"
            else:
                return f"[{self.hd}, {j}]"
# équivalent à :: en OCaml
def insert(hd, tl: ListeChainee) -> ListeChainee:
    """ Insère hd en début de la liste chainée tl."""
    return ListeChainee(hd=hd, tl=tl)
# liste vide, puis des listes plus grandes
vide = ListeChainee()   # []
l_1   = insert(1, vide)  # 1 :: [] ~= [1]
l_12  = insert(2, l_1)   # 2 :: 1 :: [] ~= [2, 1]
l_123 = insert(3, l_12)  # 3 :: 2 :: 1 :: []
print(vide)     # []
print(l_1)      # 1 :: []
print(l_12)     # 2 :: 1 :: []
print(l_123)    # 3 :: 2 :: 1 :: []
print(vide.jolie())     # []
print(l_1.jolie())      # [1]
print(l_12.jolie())     # [2, 1]
print(l_123.jolie())    # [3, 2, 1]<jupyter_output>[]
[1]
[2, 1]
[3, 2, 1]<jupyter_text>Exercice 1 : `taille`Par exemple la longueur sera bien en O(n) si n=taille(liste) avec cette approche récursive :<jupyter_code>from typing import Optional
def taille(liste: Optional[ListeChainee]) -> int:
    if liste is None:
        return 0
    elif liste.tl is None:
        return 0 if liste.hd is None else 1
    return 1 + taille(liste.tl)
print(taille(vide))   # 0
print(taille(l_1))    # 1
print(taille(l_12))   # 2
print(taille(l_123))  # 3<jupyter_output>0
1
2
3<jupyter_text>Exercice 2 : `concat`Je vais déjà commencer par écrire une fonction `copy` qui permet de copier récursivement une liste simplement chaînée, pour être sûr que l'on ne modifie pas en place une des listes données en argument.<jupyter_code>def copy(liste: ListeChainee) -> ListeChainee:
    if liste.tl is None:
        return ListeChainee(hd=liste.hd, tl=None)
    else:
        return ListeChainee(hd=liste.hd, tl=copy(liste.tl))<jupyter_output><empty_output><jupyter_text>On peut vérifier que cela marche en regardant, par exemple, l'`id` de deux objets si le deuxième est une copie du premier : les `id` seront bien différents.<jupyter_code>print(id(vide))
print(id(copy(vide)))<jupyter_output>140493199182984
140493191884136<jupyter_text>Et donc pour concaténer deux chaînes, c'est facile :<jupyter_code>def concat(liste1: ListeChainee, liste2: ListeChainee) -> ListeChainee:
    if taille(liste1) == 0:
        return liste2
    elif taille(liste2) == 0:
        return liste1
    # nouvelle liste : comme ça changer queue.tl ne modifie PAS liste1
    resultat = copy(liste1)
    queue = resultat
    while taille(queue.tl) > 0:
        queue = queue.tl
    assert taille(queue.tl) == 0
    queue.tl = ListeChainee(hd=liste2.hd, tl=liste2.tl)
    return resultat
print(concat(vide, l_1))
print(vide)  # pas modifiée : []
print(l_1)   # pas modifiée : 1 :: []
concat(l_1, l_12)  # 1 :: 2 :: 1 :: []
concat(l_1, l_123)  # 1 :: 3 :: 2 :: 1 :: []
concat(l_1, vide)   # 1 :: []
concat(l_12, vide)   # 2 :: 1 :: []
concat(l_12, l_1)   # 2 :: 1 :: 1 :: []
concat(l_123, l_123)   # 3 :: 2 :: 1 :: 3 :: 2 :: 1 :: []<jupyter_output><empty_output><jupyter_text>Exercice 3 : `appartient`C'est en complexité linéaire dans le pire des cas.<jupyter_code>def appartient(x, liste: ListeChainee) -> bool:
    if liste.hd is None:
        return False
    else:
        if liste.hd == x:
            return True
        else:
            return appartient(x, liste.tl)
assert appartient(0, vide)  == False
assert appartient(0, l_1)   == False
assert appartient(0, l_12)  == False
assert appartient(0, l_123) == False
assert appartient(1, l_1)   == True
assert appartient(1, l_12)  == True
assert appartient(1, l_123) == True
assert appartient(2, l_1)   == False
assert appartient(2, l_12)  == True
assert appartient(2, l_123) == True
assert appartient(3, l_1)   == False
assert appartient(3, l_12)  == False
assert appartient(3, l_123) == True<jupyter_output><empty_output><jupyter_text>Exercice 4 : `miroir`Ce sera en temps quadratique, à cause de toutes les recopies :<jupyter_code>def miroir(liste: ListeChainee) -> ListeChainee:
    if taille(liste) <= 1:
        return copy(liste)
    else:
        hd, tl = liste.hd, copy(liste.tl)  # O(n)
        juste_hd = ListeChainee(hd=hd, tl=None)  # O(1)
        return concat(miroir(tl), juste_hd)  # O(n^2) + O(n) à cause de concat
print(miroir(vide))   # [] => []
print(miroir(l_1))    # [1] => [1]
print(miroir(l_12))   # [2, 1] => [1, 2]
print(miroir(l_123))  # [3, 2, 1] => [1, 2, 3]<jupyter_output>[]
1 :: []
1 :: 2 :: []
1 :: 2 :: 3 :: []<jupyter_text>Exercice 5 : `alterne` La sémantique n'était pas très claire, mais on peut imaginer quelque chose comme ça :- si une des deux listes est vide, on prend l'autre,- si les deux ne sont pas vide, on prend le début de l1, de l2, puis alterne(queue l1, queue l2)<jupyter_code>def alterne(liste1: ListeChainee, liste2: ListeChainee) -> ListeChainee:
    if taille(liste1) == 0:
        return copy(liste2)  # on recopie pour ne rien modifier
    if taille(liste2) == 0:
        return copy(liste1)  # on recopie pour ne rien modifier
    h1, t1 = liste1.hd, liste1.tl  
    h2, t2 = liste2.hd, liste2.tl
    return insert(h1, insert(h2, alterne(t1, t2)))
print(alterne(l_1, l_12))     # [1, 2, 1]
print(alterne(l_12, l_1))     # [2, 1, 1]
print(alterne(l_123, l_1))    # [3, 1, 2, 1]
print(alterne(l_123, l_12))   # [3, 2, 2, 1, 1]
print(alterne(l_123, l_123))  # [3, 3, 2, 2, 1, 1]
print(alterne(l_12, l_123))   # [2, 3, 1, 2, 1]
print(alterne(l_1, l_123))    # [1, 3, 2, 1]<jupyter_output>1 :: 2 :: 1 :: []
2 :: 1 :: 1 :: []
3 :: 1 :: 2 :: 1 :: []
3 :: 2 :: 2 :: 1 :: 1 :: []
3 :: 3 :: 2 :: 2 :: 1 :: 1 :: []
2 :: 3 :: 1 :: 2 :: 1 :: []
1 :: 3 :: 2 :: 1 :: []<jupyter_text>La complexité est quadratique en $\mathcal{O}((\max(|\text{liste 1}|, |\text{liste 2}|)^2)$ à cause des recopies.  Exercice 6 : `nb_occurrences`Ce sera en temps linéaire, dans tous les cas.<jupyter_code>def nb_occurrences(x, liste: ListeChainee) -> int:
    if liste is None or liste.hd is None:
        return 0
    else:
        count = 1 if x == liste.hd else 0
    if liste.tl is None:
        return count
    else:
        return count + nb_occurrences(x, liste.tl)
assert nb_occurrences(1, vide) == 0
assert nb_occurrences(1, l_1) == 1
assert nb_occurrences(1, l_12) == 1
assert nb_occurrences(2, l_12) == 1
assert nb_occurrences(1, l_123) == 1
assert nb_occurrences(2, l_123) == 1
assert nb_occurrences(3, l_123) == 1
assert nb_occurrences(1, concat(l_1, l_1)) == 2
assert nb_occurrences(2, concat(l_1, l_12)) == 1
assert nb_occurrences(3, concat(l_12, l_1)) == 0
assert nb_occurrences(1, concat(l_12, l_12)) == 2
assert nb_occurrences(2, concat(l_12, l_12)) == 2
assert nb_occurrences(1, concat(l_123, concat(l_1, l_1))) == 3
assert nb_occurrences(2, concat(l_123, concat(l_1, l_12))) == 2
assert nb_occurrences(3, concat(l_123, concat(l_12, l_1))) == 1
assert nb_occurrences(3, concat(l_123, concat(l_12, l_12))) == 1<jupyter_output><empty_output><jupyter_text>On peut facilement écrire une variante qui sera récursive terminale ("tail recursive") :<jupyter_code>def nb_occurrences(x, liste: ListeChainee, count=0) -> int:
    if liste is None or liste.hd is None:
        return count
    else:
        count += 1 if x == liste.hd else 0
        if liste.tl is None:
            return count
        else:
            return nb_occurrences(x, liste.tl, count=count)<jupyter_output><empty_output><jupyter_text>Exercice 7 : `pairs`C'est un filtrage par le prédicat `x % 2 == 0`.Autant écrire la fonction de filtrage générique :<jupyter_code>def filtrer(liste: ListeChainee, predicate) -> ListeChainee:
    if liste is None or liste.hd is None:  # liste de taille 0
        return ListeChainee(hd=None, tl=None)
    elif liste.tl is None:  # liste de taille 1
        if predicate(liste.hd):  # on renvoie [hd]
            return ListeChainee(hd=liste.hd, tl=None)
        else:  # on renvoie []
            return ListeChainee(hd=None, tl=None)
    else:  # liste de taille >= 2
        if predicate(liste.hd):
            return insert(liste.hd, filtrer(liste.tl, predicate))
        else:
            return filtrer(liste.tl, predicate)<jupyter_output><empty_output><jupyter_text>Et donc c'est rapide :<jupyter_code>def pairs(liste: ListeChainee) -> ListeChainee:
    def predicate(x):
        return (x % 2) == 0
    # aussi : predicate = lambda x: (x % 2) == 0
    return filtrer(liste, predicate)
def impairs(liste: ListeChainee) -> ListeChainee:
    def predicate(x):
        return (x % 2) == 1
    return filtrer(liste, predicate)
print(pairs(vide))   # []
print(pairs(l_1))    # []
print(pairs(l_12))   # [2]
print(pairs(l_123))  # [2]
print(pairs(insert(4, insert(6, insert(8, l_123)))))  # [4, 6, 8, 2]
print(pairs(insert(5, insert(6, insert(8, l_123)))))  # [6, 8, 2]
print(impairs(vide))   # []
print(impairs(l_1))    # [1]
print(impairs(l_12))   # [1]
print(impairs(l_123))  # [3, 1]
print(impairs(insert(4, insert(6, insert(8, l_123)))))  # [3, 1]
print(impairs(insert(5, insert(6, insert(8, l_123)))))  # [5, 3, 1]<jupyter_output>[]
1 :: []
1 :: []
3 :: 1 :: []
3 :: 1 :: []
5 :: 3 :: 1 :: []<jupyter_text>Exercice 8 : `range`Ce sera de complexité temporelle linéaire :<jupyter_code>def myrange(n: int) -> ListeChainee:
    if n <= 0:
        return ListeChainee(hd=None, tl=None)
    elif n == 1:
        return ListeChainee(hd=1, tl=None)
        # return insert(1, vide)
    else:
        return ListeChainee(hd=n, tl=myrange(n-1))
print(myrange(1))  # [1]
print(myrange(2))  # [1, 2]
print(myrange(3))  # [1, 2, 3]
print(myrange(4))  # [1, 2, 3, 4]<jupyter_output>1 :: []
2 :: 1 :: []
3 :: 2 :: 1 :: []
4 :: 3 :: 2 :: 1 :: []<jupyter_text>Si on veut les avoir dans l'ordre croissant, il faudrait utiliser `miroir` qui est quadratique.Autant écrire directement une fonction `intervale(a, b)` qui renvoie la liste simplement chaînée contenant `a :: (a+1) :: ... :: b` :<jupyter_code>def intervale(a: int, b: Optional[int]=None) -> ListeChainee:
    if b is None:
        a, b = 1, a
    n = b - a
    if n < 0:     # [a..b] = []
        return ListeChainee(hd=None, tl=None)
    elif n == 0:  # [a..b] = [a]
        return ListeChainee(hd=a, tl=None)
    else:         # [a..b] = a :: [a+1..b]
        return ListeChainee(hd=a, tl=intervale(a+1, b))
print(intervale(10))      # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(intervale(1, 4))    # [1, 2, 3, 4]
print(intervale(13, 13))  # [13]
print(intervale(13, 10))  # []<jupyter_output>1 :: 2 :: 3 :: 4 :: 5 :: 6 :: 7 :: 8 :: 9 :: 10 :: []
1 :: 2 :: 3 :: 4 :: []
13 :: []
[]<jupyter_text>Une autre approche est d'écrire la fonction `mymap` et de dire que```pythonintervale_bis(a, b) = miroir(mymap(lambda x: x + (a - 1), myrange(b - a + 1)))```<jupyter_code>from typing import Callable

def mymap(fonction: Callable, liste: ListeChainee) -> ListeChainee:
    if liste is None or liste.hd is None:  # liste de taille 0
        return ListeChainee(hd=None, tl=None)
    elif liste.tl is None:  # liste de taille 1
        return ListeChainee(hd=fonction(liste.hd), tl=None)
    else:  # liste de taille >= 2
        return ListeChainee(hd=fonction(liste.hd), tl=mymap(fonction, liste.tl))
print(myrange(10))
print(mymap(lambda x: x, myrange(10)))

def intervale_bis(a: int, b: int) -> ListeChainee:
    return miroir(mymap(lambda x: x + (a - 1), myrange(b - a + 1)))
print(intervale_bis(1, 10))   # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(intervale_bis(1, 4))    # [1, 2, 3, 4]
print(intervale_bis(13, 13))  # [13]
print(intervale_bis(13, 10))  # []<jupyter_output>1 :: 2 :: 3 :: 4 :: 5 :: 6 :: 7 :: 8 :: 9 :: 10 :: []
1 :: 2 :: 3 :: 4 :: []
13 :: []
[]<jupyter_text>Exercice 9 : `premiers`Plusieurs possibilités. Un filtre d'Erathosthène marche bien, ou une filtrage.Je ne vais pas utiliser de tableaux donc on est un peu réduit d'utiliser une filtrage.On a besoin des fonctions suivantes :- calculer la racine entière de $n$, très facile par une boucle,- calculer les nombres impairs entre 5 et $\lfloor \sqrt{n} \rfloor$,- filtrer cette liste de nombres impairs pour garder ceux qui divisent $n$,- et dire que $n$ est premier s'il a un diviseur non trivial.<jupyter_code>def racine(n: int) -> int:
    i = 1
    for i in range(n + 1):
        if i*i > n:
            return i - 1
    return i

print(racine(1))  # 1
print(racine(5))  # 2
print(racine(102))  # 10
print(racine(120031))  # 346
def intervale2(a: int, b: Optional[int]=None, pas: int=1) -> ListeChainee:
    if b is None:
        a, b = 1, a
    n = b - a
    if n < 0:     # [a..b::p] = []
        return ListeChainee(hd=None, tl=None)
    elif n == 0:  # [a..b::p] = [a]
        return ListeChainee(hd=a, tl=None)
    else:         # [a..b::p] = a :: [a+p..b::p]
        return ListeChainee(hd=a, tl=intervale2(a + pas, b=b, pas=pas))
print(intervale2(1, 10, 2))      # [1, 3, 5, 7, 9]
print(intervale2(1, 4, 2))    # [1, 3]
print(intervale2(13, 13, 2))  # [13]
print(intervale2(13, 10, 2))  # []<jupyter_output>1 :: 3 :: 5 :: 7 :: 9 :: []
1 :: 3 :: []
13 :: []
[]<jupyter_text>Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne.<jupyter_code>def estDivisible(n: int, k: int) -> bool:
    return (n % k) == 0
estDivisible(10, 2)
estDivisible(10, 3)
estDivisible(10, 4)
estDivisible(10, 5)<jupyter_output><empty_output><jupyter_text>On est prêt à écrire `estPremier` :<jupyter_code>def estPremier(n : int) -> bool:
    return taille(filtrer(intervale2(2, racine(n), 1), lambda k: estDivisible(n, k))) == 0<jupyter_output><empty_output><jupyter_text>En effet il suffit de construire d'abord la liste des entiers impairs de 2 à $\lfloor \sqrt{n} \rfloor$, de les filtrer par ceux qui divisent $n$, et de vérifier si on a aucun diviseur (`taille(..) == 0`) auquel cas $n$ est premier, ou si $n$ a au moins un diviseur auquel cas $n$ n'est pas premier.<jupyter_code>for n in range(2, 20):
    print("Petits diviseurs de", n, " -> ", filtrer(intervale2(2, racine(n), 1), lambda k: estDivisible(n, k)))<jupyter_output>Petits diviseurs de 2  ->  []
Petits diviseurs de 3  ->  []
Petits diviseurs de 4  ->  2 :: []
Petits diviseurs de 5  ->  []
Petits diviseurs de 6  ->  2 :: []
Petits diviseurs de 7  ->  []
Petits diviseurs de 8  ->  2 :: []
Petits diviseurs de 9  ->  3 :: []
Petits diviseurs de 10  ->  2 :: []
Petits diviseurs de 11  ->  []
Petits diviseurs de 12  ->  2 :: 3 :: []
Petits diviseurs de 13  ->  []
Petits diviseurs de 14  ->  2 :: []
Petits diviseurs de 15  ->  3 :: []
Petits diviseurs de 16  ->  2 :: 4 :: []
Petits diviseurs de 17  ->  []
Petits diviseurs de 18  ->  2 :: 3 :: []
Petits diviseurs de 19  ->  []<jupyter_text>On voit dans l'exemple ci dessus les nombres premiers comme ceux n'ayant aucun diviseurs, et les nombres non premiers comme ceux ayant au moins un diviseur.<jupyter_code>def premiers(n : int) -> ListeChainee:
    return filtrer(intervale2(2, n, 1), estPremier)
premiers(10)  # [2, 3, 5, 7]
premiers(100)  # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]<jupyter_output><empty_output><jupyter_text>---- Quelques tris par comparaison On fera les tris en ordre croissant.<jupyter_code>test = [3, 1, 8, 4, 5, 6, 1, 2]<jupyter_output><empty_output><jupyter_text>Exercice 10 : Tri insertion<jupyter_code>from typing import TypeVar, List
_a = TypeVar('alpha')

def insere(x : _a, liste : List[_a]) -> List[_a]:
    if len(liste) == 0:
        return [x]
    else:
        t, q = liste[0], liste[1:]
        if x <= t:
            return [x] + liste
        else:
            return [t] + insere(x, q)
def tri_insertion(liste : List[_a]) -> List[_a]:
    if len(liste) == 0:
        return []
    else:
        t, q = liste[0], liste[1:]
        return insere(t, tri_insertion(q))
tri_insertion(test)<jupyter_output><empty_output><jupyter_text>Complexité en temps $\mathcal{O}(n^2)$.  Exercice 11 : Tri insertion générique<jupyter_code>from typing import TypeVar, List, Callable
_a = TypeVar('alpha')

def insere2(ordre : Callable[[_a, _a], bool], x : _a, liste : List[_a]) -> List[_a]:
    if len(liste) == 0:
        return [x]
    else:
        t, q = liste[0], liste[1:]
        if ordre(x, t):
            return [x] + liste
        else:
            return [t] + insere2(ordre, x, q)
def tri_insertion2(ordre : Callable[[_a, _a], bool], liste : List[_a]) -> List[_a]:
    if len(liste) == 0:
        return []
    else:
        t, q = liste[0], liste[1:]
        return insere2(ordre, t, tri_insertion2(ordre, q))
ordre_croissant = lambda x, y: x <= y
tri_insertion2(ordre_croissant, test)
ordre_decroissant = lambda x, y: x >= y
tri_insertion2(ordre_decroissant, test)<jupyter_output><empty_output><jupyter_text>Exercice 12 : Tri selection<jupyter_code>from typing import TypeVar, List, Tuple
_a = TypeVar('alpha')

def selectionne_min(liste : List[_a]) -> Tuple[_a, List[_a]]:
    if len(liste) == 0:
        raise ValueError("Selectionne_min sur liste vide")
    else:
        def cherche_min(mini : _a, autres : List[_a], reste : List[_a]) -> Tuple[_a, List[_a]]:
            if len(reste) == 0:
                return (mini, autres)
            else:
                t, q = reste[0], reste[1:]
                if t < mini:
                    return cherche_min(t, [mini] + autres, q)
                else:
                    return cherche_min(mini, [t] + autres, q)
        t, q = liste[0], liste[1:]
        return cherche_min(t, [], q)
test
selectionne_min(test)<jupyter_output><empty_output><jupyter_text>(On voit que la liste `autre` a été inversée)<jupyter_code>def tri_selection(liste : List[_a]) -> List[_a]:
    if len(liste) == 0:
        return []
    else:
        mini, autres = selectionne_min(liste)
        return [mini] + tri_selection(autres)
tri_selection(test)<jupyter_output><empty_output><jupyter_text>Complexité en temps : $\mathcal{O}(n^2)$.  Exercices 13, 14, 15 : Tri fusion<jupyter_code>from typing import TypeVar, List, Tuple
_a = TypeVar('alpha')

def separe(liste : List[_a]) -> Tuple[List[_a], List[_a]]:
    if len(liste) == 0:
        return ([], [])
    elif len(liste) == 1:
        return ([liste[0]], [])
    else:
        x, y, q = liste[0], liste[1], liste[2:]
        a, b = separe(q)
        return ([x] + a, [y] + b)
test
separe(test)
def fusion(liste1 : List[_a], liste2 : List[_a]) -> List[_a]:
    if (len(liste1), len(liste2)) == (0, 0):
        return []
    elif len(liste1) == 0:
        return liste2
    elif len(liste2) == 0:
        return liste1
    else:  # les deux sont non vides
        x, a = liste1[0], liste1[1:]
        y, b = liste2[0], liste2[1:]
        if x <= y:
            return [x] + fusion(a, [y] + b)
        else:
            return [y] + fusion([x] + a, b)

        
fusion([1, 3, 7], [2, 3, 8])
def tri_fusion(liste : List[_a]) -> List[_a]:
    if len(liste) <= 1:
        return liste
    else:
        a, b = separe(liste)
        return fusion(tri_fusion(a), tri_fusion(b))
tri_fusion(test)<jupyter_output><empty_output><jupyter_text>Complexité en temps $\mathcal{O}(n \log n)$.  Comparaisons<jupyter_code>%timeit tri_insertion(test)
%timeit tri_selection(test)
%timeit tri_fusion(test)
from sys import setrecursionlimit
setrecursionlimit(100000)
# nécessaire pour tester les différentes fonctions récursives sur de grosses listes
import random

def test_random(n : int) -> List[int]:
    return [random.randint(-1000, 1000) for _ in range(n)]

for n in [10, 100, 1000]:
    print("\nFor n =", n)
    for tri in [tri_insertion, tri_selection, tri_fusion]:
        print("    and tri = {}".format(tri.__name__))
        %timeit tri(test_random(n))<jupyter_output>For n = 10
    and tri = tri_insertion
33.2 µs ± 4.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    and tri = tri_selection
85.8 µs ± 4.57 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
    and tri = tri_fusion
59.6 µs ± 5.57 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

For n = 100
    and tri = tri_insertion
2.01 ms ± 93.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    and tri = tri_selection
4.32 ms ± 123 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
    and tri = tri_fusion
1.12 ms ± 10.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

For n = 1000
    and tri = tri_insertion
758 ms ± 18.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    and tri = tri_selection
1.54 s ± 43.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
    and tri = tri_fusion
26.1 ms ± 631 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)<jupyter_text>- C'est assez pour vérifier que le tri fusion est **bien plus efficace** que les autres.- On voit aussi que les tris par insertion et sélection sont pire que linéaires,- Mais que le tri par fusion est presque linéaire (pour $n$ petits, $n \log n$ est presque linéaire). ---- Listes : l'ordre supérieurJe ne corrige pas les questions qui étaient traitées dans le TP1.  Exercice 16 : `applique`<jupyter_code>from typing import TypeVar, List, Callable
_a, _b = TypeVar('_a'), TypeVar('_b')

def applique(f : Callable[[_a], _b], liste : List[_a]) -> List[_b]:
    # Triche :
    return list(map(f, liste))
    # 1ère approche :
    return [f(x) for x in liste]
    # 2ème approche :
    fliste = []
    for x in liste:
        fliste.append(f(x))
    return fliste
    # 3ème approche
    n = len(liste)
    if n == 0: return []
    fliste = [liste[0] for _ in range(n)]
    for i in range(n):
        fliste[i] = f(liste[i])
    return fliste<jupyter_output><empty_output><jupyter_text>Exercice 17<jupyter_code>def premiers_carres_parfaits(n : int) -> List[int]:
    return applique(lambda x : x * x, list(range(1, n + 1)))
premiers_carres_parfaits(12)<jupyter_output><empty_output><jupyter_text>Exercice 18 : `itere`<jupyter_code>from typing import TypeVar, List, Callable
_a = TypeVar('_a')

def itere(f : Callable[[_a], None], liste : List[_a]) -> None:
    for x in liste:
        f(x)<jupyter_output><empty_output><jupyter_text>Exercice 19<jupyter_code>print_int = lambda i: print("{}".format(i))
def affiche_liste_entiers(liste : List[int]) -> None:
    print("Debut")
    itere(print_int, liste)
    print("Fin")

affiche_liste_entiers([1, 2, 4, 5, 12011993])<jupyter_output>Debut
1
2
4
5
12011993
Fin<jupyter_text>Exercice 20 : `qqsoit` et `ilexiste`<jupyter_code>from typing import TypeVar, List, Callable
_a = TypeVar('_a')

# Comme all(map(f, liste))
def qqsoit(f : Callable[[_a], bool], liste : List[_a]) -> bool:
    for x in liste:
        if not f(x): return False   # arret preliminaire
    return True
# Comme any(map(f, liste))
def ilexiste(f : Callable[[_a], bool], liste : List[_a]) -> bool:
    for x in liste:
        if f(x): return True   # arret preliminaire
    return False
qqsoit(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
ilexiste(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
%timeit qqsoit(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
%timeit all(map(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5]))
%timeit ilexiste(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
%timeit any(map(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5]))<jupyter_output>395 ns ± 41.7 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
641 ns ± 32.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)<jupyter_text>Exercice 21 : `appartient` version 2<jupyter_code>def appartient_curry(x : _a) -> Callable[[List[_a]], bool]:
    return lambda liste: ilexiste(lambda y: x == y, liste)

def appartient(x : _a, liste : List[_a]) -> bool:
    return ilexiste(lambda y: x == y, liste)
def toutes_egales(x : _a, liste : List[_a]) -> bool:
    return qqsoit(lambda y: x == y, liste)
appartient_curry(1)([1, 2, 3])

appartient(1, [1, 2, 3])
appartient(5, [1, 2, 3])

toutes_egales(1, [1, 2, 3])
toutes_egales(5, [1, 2, 3])<jupyter_output><empty_output><jupyter_text>Est-ce que notre implémentation peut être plus rapide que le test `x in liste` ?Non, mais elle est aussi rapide. C'est déjà pas mal !<jupyter_code>%timeit appartient(random.randint(-10, 10), [random.randint(-1000, 1000) for _ in range(1000)])
%timeit random.randint(-10, 10) in [random.randint(-1000, 1000) for _ in range(1000)]<jupyter_output>1.17 ms ± 25.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
1.1 ms ± 10.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)<jupyter_text>Exercice 22 : `filtre`<jupyter_code>from typing import TypeVar, List, Callable
_a = TypeVar('_a')

# Comme list(filter(f, liste))
def filtre(f : Callable[[_a], bool], liste : List[_a]) -> List[_a]:
    # return [x for x in liste if f(x)]
    liste2 = []
    for x in liste:
        if f(x):
            liste2.append(x)
    return liste2
filtre(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
filtre(lambda x: (x % 2) != 0, [1, 2, 3, 4, 5])<jupyter_output><empty_output><jupyter_text>Exercice 23Je vous laisse trouver pour `premiers`.<jupyter_code>pairs   = lambda liste: filtre(lambda x: (x % 2) == 0, liste)
impairs = lambda liste: filtre(lambda x: (x % 2) != 0, liste)
pairs(list(range(10)))
impairs(list(range(10)))<jupyter_output><empty_output><jupyter_text>Exercice 24 : `reduit`<jupyter_code>from typing import TypeVar, List, Callable
_a = TypeVar('_a')

# Comme list(filter(f, liste))
def reduit_rec(f : Callable[[_a, _b], _a], acc : _a, liste : List[_b]) -> _a:
    if len(liste) == 0:
        return acc
    else:
        h, q = liste[0], liste[1:]
        return reduit(f, f(acc, h), q)

# Version non récursive, bien plus efficace
def reduit(f : Callable[[_a, _b], _a], acc : _a, liste : List[_b]) -> _a:
    acc_value = acc
    for x in liste:
        acc_value = f(acc_value, x)
    return acc_value<jupyter_output><empty_output><jupyter_text>Très pratique pour calculer des sommes, notamment.  Exercice 25 : `somme`, `produit`<jupyter_code>from operator import add
somme_rec = lambda liste: reduit_rec(add, 0, liste)
somme = lambda liste: reduit(add, 0, liste)

somme_rec(list(range(10)))
somme(list(range(10)))
sum(list(range(10)))
%timeit somme_rec(list(range(10)))
%timeit somme(list(range(10)))
%timeit sum(list(range(10)))<jupyter_output>1.59 µs ± 16.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
1.42 µs ± 85.8 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
644 ns ± 7.56 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)<jupyter_text>Pour de petites listes, la version récursive est aussi efficace que la version impérative. Chouette !<jupyter_code>%timeit somme_rec(list(range(1000)))
%timeit somme(list(range(1000)))
%timeit sum(list(range(1000)))
from operator import mul
produit = lambda liste: reduit(mul, 1, liste)

produit(list(range(1, 6)))  # 5! = 120<jupyter_output><empty_output><jupyter_text>Bonus :<jupyter_code>def factorielle(n : int) -> int:
    return produit(range(1, n + 1))

for n in range(1, 15):
    print("{:>7}! = {:>13}".format(n, factorielle(n)))<jupyter_output>1! =             1
      2! =             2
      3! =             6
      4! =            24
      5! =           120
      6! =           720
      7! =          5040
      8! =         40320
      9! =        362880
     10! =       3628800
     11! =      39916800
     12! =     479001600
     13! =    6227020800
     14! =   87178291200<jupyter_text>Exercice 26 : `miroir` version 2<jupyter_code>miroir = lambda liste: reduit(lambda l, x : [x] + l, [], liste)
miroir([2, 3, 5, 7, 11])<jupyter_output><empty_output><jupyter_text>**Attention** en Python, les listes ne sont PAS simplement chainées, donc `lambda l, x : [x] + l` est en temps **linéaire** en $|l| = n$, pas en $\mathcal{O}(1)$ comme en Caml/OCaml pour `fun l x -> x :: l`. ---- Arbres /!\ Les deux dernières parties sont **bien plus difficiles** en Python qu'en Caml.  Exercice 27<jupyter_code>from typing import Dict, Optional, Tuple

# Impossible de définir un type récursivement, pas comme en Caml
arbre_bin = Dict[str, Optional[Tuple[Dict, Dict]]]
from pprint import pprint
arbre_test = {'Noeud': (
        {'Noeud': (
            {'Noeud': (
                {'Feuille': None},
                {'Feuille': None}
            )},
            {'Feuille': None}
        )},
        {'Feuille': None}
    )}
pprint(arbre_test)<jupyter_output>{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
                      {'Feuille': None})},
           {'Feuille': None})}<jupyter_text>Avec une syntaxe améliorée, on se rapproche de très près de la syntaxe de Caml/OCaml :<jupyter_code>Feuille = {'Feuille': None}
Noeud = lambda x, y : {'Noeud': (x, y)}
arbre_test = Noeud(Noeud(Noeud(Feuille, Feuille), Feuille), Feuille)
pprint(arbre_test)<jupyter_output>{'Noeud': ({'Noeud': ({'Noeud': ({'Feuille': None}, {'Feuille': None})},
                      {'Feuille': None})},
           {'Feuille': None})}<jupyter_text>Exercice 28 Compte le nombre de feuilles et de sommets.<jupyter_code>def taille(a : arbre_bin) -> int:
    # Pattern matching ~= if, elif,.. sur les clés de la profondeur 1
    # du dictionnaire (une seule clé)
    if 'Feuille' in a:
        return 1
    elif 'Noeud' in a:
        x, y = a['Noeud']
        return 1 + taille(x) + taille(y)
taille(arbre_test)  # 7<jupyter_output><empty_output><jupyter_text>Exercice 29<jupyter_code>def hauteur(a : arbre_bin) -> int:
    if 'Feuille' in a:
        return 0
    elif 'Noeud' in a:
        x, y = a['Noeud']
        return 1 + max(hauteur(x), hauteur(y))
hauteur(arbre_test)  # 3<jupyter_output><empty_output><jupyter_text>Exercice 30 Bonus. (Écrivez une fonction testant si un arbre étiqueté par des entiers est tournoi.) ---- Parcours d'arbres binaires Après quelques exercices manipulant cette structure de dictionnaire, écrire la suite n'est pas trop difficile.  Exercice 31<jupyter_code>from typing import TypeVar, Union, List

F = TypeVar('F')
N = TypeVar('N')

element_parcours = Union[F, N]
parcours = List[element_parcours]<jupyter_output><empty_output><jupyter_text>Exercice 32 : Parcours naifs (complexité quadratique)<jupyter_code>def parcours_prefixe(a : arbre_bin) -> parcours:
    if 'Feuille' in a:
        return [F]
    elif 'Noeud' in a:
        g, d = a['Noeud']
        return [N] + parcours_prefixe(g) + parcours_prefixe(d)

parcours_prefixe(arbre_test)
def parcours_postfixe(a : arbre_bin) -> parcours:
    if 'Feuille' in a:
        return [F]
    elif 'Noeud' in a:
        g, d = a['Noeud']
        return parcours_postfixe(g) + parcours_postfixe(d) + [N]

parcours_postfixe(arbre_test)
def parcours_infixe(a : arbre_bin) -> parcours:
    if 'Feuille' in a:
        return [F]
    elif 'Noeud' in a:
        g, d = a['Noeud']
        return parcours_infixe(g) + [N] + parcours_infixe(d)

parcours_infixe(arbre_test)<jupyter_output><empty_output><jupyter_text>Pourquoi ont-ils une complexité quadratique ? La concaténation (`@` en OCaml, `+` en Python) ne se fait pas en temps constant mais linéaire dans la taille de la plus longue liste.  Exercice 33 : Parcours linéairesOn ajoute une fonction auxiliaire et un argument `vus` qui est une liste qui stocke les élements observés dans l'ordre du parcours<jupyter_code>def parcours_prefixe2(a : arbre_bin) -> parcours:
    def parcours(vus, b):
        if 'Feuille' in b:
            vus.insert(0, F)
            return vus
        elif 'Noeud' in b:
            vus.insert(0, N)
            g, d = b['Noeud']
            return parcours(parcours(vus, g), d)
    p = parcours([], a)
    return p[::-1]

parcours_prefixe2(arbre_test)
def parcours_postfixe2(a : arbre_bin) -> parcours:
    def parcours(vus, b):
        if 'Feuille' in b:
            vus.insert(0, F)
            return vus
        elif 'Noeud' in b:
            g, d = b['Noeud']
            p = parcours(parcours(vus, g), d)
            p.insert(0, N)
            return p
    p = parcours([], a)
    return p[::-1]

parcours_postfixe2(arbre_test)
def parcours_infixe2(a : arbre_bin) -> parcours:
    def parcours(vus, b):
        if 'Feuille' in b:
            vus.insert(0, F)
            return vus
        elif 'Noeud' in b:
            g, d = b['Noeud']
            p = parcours(vus, g)
            p.insert(0, N)
            return parcours(p, d)
    p = parcours([], a)
    return p[::-1]

parcours_infixe2(arbre_test)<jupyter_output><empty_output><jupyter_text>Exercice 34 : parcours en largeur et en profondeur Pour utiliser une file de priorité (*priority queue*), on utilise le module [collections.deque](https://docs.python.org/3/library/collections.htmlcollections.deque).<jupyter_code>from collections import deque

def parcours_largeur(a : arbre_bin) -> parcours:
    file = deque()
    # fonction avec effet de bord sur la file
    def vasy() -> parcours:
        if len(file) == 0:
            return []
        else:
            b = file.pop()
            if 'Feuille' in b:
                # return [F] + vasy()
                v = vasy()
                v.insert(0, F)
                return v
            elif 'Noeud' in b:
                g, d = b['Noeud']
                file.insert(0, g)
                file.insert(0, d)
                # return [N] + vasy()
                v = vasy()
                v.insert(0, N)
                return v
    file.insert(0, a)
    return vasy()

parcours_largeur(arbre_test)<jupyter_output><empty_output><jupyter_text>En remplaçant la file par une pile (une simple `list`), on obtient le parcours en profondeur, avec la même complexité.<jupyter_code>def parcours_profondeur(a : arbre_bin) -> parcours:
    pile = []
    # fonction avec effet de bord sur la file
    def vasy() -> parcours:
        if len(pile) == 0:
            return []
        else:
            b = pile.pop()
            if 'Feuille' in b:
                # return [F] + vasy()
                v = vasy()
                v.append(F)
                return v
            elif 'Noeud' in b:
                g, d = b['Noeud']
                pile.append(g)
                pile.append(d)
                # return [N] + vasy()
                v = vasy()
                v.insert(0, N)
                return v
    pile.append(a)
    return vasy()

parcours_profondeur(arbre_test)<jupyter_output><empty_output><jupyter_text>Exercice 35 et fin  Reconstruction depuis le parcours prefixe<jupyter_code>test_prefixe = parcours_prefixe2(arbre_test)
test_prefixe<jupyter_output><empty_output><jupyter_text>L'idée de cette solution est la suivante :j'aimerais une fonction récursive qui fasse le travail;le problème c'est que si on prend un parcours prefixe, soit il commencepar F et l'arbre doit être une feuille; soit il est de la forme N::qoù q n'est plus un parcours prefixe mais la concaténation de DEUX parcoursprefixe, on ne peut donc plus appeler la fonction sur q.On va donc écrire une fonction qui prend une liste qui contient plusieursparcours concaténé et qui renvoie l'arbre correspondant au premier parcourset ce qui n'a pas été utilisé :<jupyter_code>from typing import Tuple

def reconstruit_prefixe(par : parcours) -> arbre_bin:
    def reconstruit(p : parcours) -> Tuple[arbre_bin, parcours]:
        if len(p) == 0:
            raise ValueError("parcours invalide pour reconstruit_prefixe")
        elif p[0] == F:
            return (Feuille, p[1:])
        elif p[0] == N:
            g, q = reconstruit(p[1:])
            d, r = reconstruit(q)
            return (Noeud(g, d), r)
    # call it
    a, p = reconstruit(par)
    if len(p) == 0:
        return a
    else:
        raise ValueError("parcours invalide pour reconstruit_prefixe")
reconstruit_prefixe([F])
reconstruit_prefixe(test_prefixe)<jupyter_output><empty_output><jupyter_text>Et cet exemple va échouer :<jupyter_code>reconstruit_prefixe([N, F, F] + test_prefixe)  # échoue<jupyter_output><empty_output><jupyter_text>Reconstruction depuis le parcours en largeur Ce n'est pas évident quand on ne connait pas. L'idée est de se servir d'une filepour stocker les arbres qu'on reconstruit peu à peu depuis les feuilles. La filepermet de récupérer les bons sous-arbres quand on rencontre un noeud<jupyter_code>largeur_test = parcours_largeur(arbre_test)
largeur_test
from collections import deque

def reconstruit_largeur(par : parcours) -> arbre_bin:
    file = deque()
    # Fonction avec effets de bord
    def lire_element(e : element_parcours) -> None:
        if e == F:
            file.append(Feuille)
        elif e == N:
            d = file.popleft()
            g = file.popleft()  # attention à l'ordre !
            file.append(Noeud(g, d))
    # Applique cette fonction à chaque élement du parcours
    for e in reversed(par):
        lire_element(e)
    if len(file) == 1:
        return file.popleft()
    else:
        raise ValueError("parcours invalide pour reconstruit_largeur")
largeur_test
reconstruit_largeur(largeur_test)
arbre_test<jupyter_output><empty_output><jupyter_text>Le même algorithme (enfin presque, modulo interversion de g et d)avec une pile donne une autre version de la reconstruction du parcours prefixe.<jupyter_code>from collections import deque

def reconstruit_prefixe2(par : parcours) -> arbre_bin:
    pile = deque()
    # Fonction avec effets de bord
    def lire_element(e : element_parcours) -> None:
        if e == F:
            pile.append(Feuille)
        elif e == N:
            g = pile.pop()
            d = pile.pop()  # attention à l'ordre !
            pile.append(Noeud(g, d))
    # Applique cette fonction à chaque élement du parcours
    for e in reversed(par):
        lire_element(e)
    if len(pile) == 1:
        return pile.pop()
    else:
        raise ValueError("parcours invalide pour reconstruit_prefixe2")
prefixe_test = parcours_prefixe2(arbre_test)
prefixe_test
reconstruit_prefixe2(prefixe_test)
arbre_test<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14236162832762325, 'fraction_numerical': 0.04417679228821314, 'mean_word_length': 3.2983627549620413, 'pattern_counts': {'":': 1, '<': 268, '<?xml version=': 0, '>': 364, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '68', 'dir': 'jupyter-structured-clean-dedup', 'id': '622940', 'license': 'MIT', 'n_tokens_mistral': 19683, 'n_tokens_neox': 18291, 'n_words': 5093, 'path': 'agreg/TP_Programmation_2017-18/TP2__Python.ipynb', 'repo_name': 'doc22940/notebooks-2', 'size': '46993'}