#!/usr/bin/env python
# coding: utf-8
# Table of Contents
#
# # TP 2 - Programmation pour la préparation à l'agrégation maths option info
# - En Python, version 3.
# In[4]:
from sys import version
print(version)
# ----
# # Listes
# Ces exercices sont un peu foireux : les "*listes*" en Python **ne sont pas des listes simplement chaînées** !
# ## Exercice 1 : `taille`
# In[12]:
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])
# In[7]:
len([])
len([1, 2, 3])
# ## Exercice 2 : `concat`
# In[16]:
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
# In[19]:
concatene([1, 2], [3, 4])
[1, 2] + [3, 4]
# Mais attention le typage est toujours optionnel en Python :
# In[20]:
concatene([1, 2], ["pas", "entier", "?"])
# ## Exercice 3 : `appartient`
# In[21]:
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])
# In[22]:
1 in []
1 in [1]
1 in [1, 2, 3]
4 in [1, 2, 3]
# Notre implémentation est évidemment plus lente que le test `x in liste` de la librarie standard...
# Mais pas tant :
# In[23]:
get_ipython().run_line_magic('timeit', 'appartient(1000, list(range(10000)))')
get_ipython().run_line_magic('timeit', '1000 in list(range(10000))')
# ## Exercice 4 : `miroir`
# In[26]:
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
# In[28]:
miroir([2, 3, 5, 7, 11])
[2, 3, 5, 7, 11][::-1]
# In[29]:
get_ipython().run_line_magic('timeit', 'miroir([2, 3, 5, 7, 11])')
get_ipython().run_line_magic('timeit', '[2, 3, 5, 7, 11][::-1]')
# ## Exercice 5 : `alterne`
# La sémantique n'était pas très claire, mais on peut imaginer quelque chose comme ça :
# In[30]:
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
# In[31]:
alterne([3, 5], [2, 4, 6])
alterne([1, 3, 5], [2, 4, 6])
alterne([1, 3, 5], [4, 6])
# La complexité est linéaire en $\mathcal{O}(\max(|\text{liste 1}|, |\text{liste 2}|)$.
# ## Exercice 6 : `nb_occurrences`
# In[32]:
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])
# ## Exercice 7 : `pairs`
#
# C'est un filtrage :
# In[33]:
get_ipython().run_line_magic('pinfo', 'filter')
# In[36]:
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]
# In[37]:
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])
# ## Exercice 8 : `range`
# In[84]:
from typing import List
def myrange(n : int) -> List[int]:
liste = []
i = 1
while i <= n:
liste.append(i)
i += 1
return liste
# In[85]:
myrange(4)
# In[47]:
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
# In[48]:
intervale(10)
intervale(1, 4)
# ## 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*)
# In[77]:
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)
# In[78]:
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
# In[79]:
intervale2(2, 12, 1)
intervale2(2, 12, 3)
# Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne.
# In[80]:
def estDivisible(n : int, k : int) -> bool:
return (n % k) == 0
# In[81]:
estDivisible(10, 2)
estDivisible(10, 3)
estDivisible(10, 4)
estDivisible(10, 5)
# In[107]:
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)))
# In[108]:
for n in range(2, 20):
print(n, list(map(lambda k: estDivisible(n, k), intervale2(2, racine(n), 1))))
# In[109]:
from typing import List
def premiers(n : int) -> List[int]:
return [p for p in intervale2(2, n, 1) if estPremier(p)]
# In[110]:
premiers(10)
# In[111]:
premiers(100)
# ----
# # 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.
# In[173]:
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}]"
# In[174]:
# é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)
# In[175]:
# 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 :: []
# In[176]:
print(vide) # []
print(l_1) # 1 :: []
print(l_12) # 2 :: 1 :: []
print(l_123) # 3 :: 2 :: 1 :: []
# In[177]:
print(vide.jolie()) # []
print(l_1.jolie()) # [1]
print(l_12.jolie()) # [2, 1]
print(l_123.jolie()) # [3, 2, 1]
# ## Exercice 1 : `taille`
#
# Par exemple la longueur sera bien en O(n) si n=taille(liste) avec cette approche récursive :
# In[149]:
from typing import Optional
# In[150]:
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)
# In[151]:
print(taille(vide)) # 0
print(taille(l_1)) # 1
print(taille(l_12)) # 2
print(taille(l_123)) # 3
# ## 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.
# In[152]:
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))
# 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.
# In[153]:
print(id(vide))
print(id(copy(vide)))
# Et donc pour concaténer deux chaînes, c'est facile :
# In[154]:
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
# In[156]:
print(concat(vide, l_1))
print(vide) # pas modifiée : []
print(l_1) # pas modifiée : 1 :: []
# In[135]:
concat(l_1, l_12) # 1 :: 2 :: 1 :: []
# In[136]:
concat(l_1, l_123) # 1 :: 3 :: 2 :: 1 :: []
# In[137]:
concat(l_1, vide) # 1 :: []
# In[138]:
concat(l_12, vide) # 2 :: 1 :: []
# In[139]:
concat(l_12, l_1) # 2 :: 1 :: 1 :: []
# In[140]:
concat(l_123, l_123) # 3 :: 2 :: 1 :: 3 :: 2 :: 1 :: []
# ## Exercice 3 : `appartient`
#
# C'est en complexité linéaire dans le pire des cas.
# In[141]:
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)
# In[144]:
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
# ## Exercice 4 : `miroir`
#
# Ce sera en temps quadratique, à cause de toutes les recopies :
# In[178]:
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
# In[255]:
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]
# ## 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)
# In[256]:
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)))
# In[257]:
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]
# 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.
#
# In[264]:
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)
# In[265]:
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
# On peut facilement écrire une variante qui sera récursive terminale ("tail recursive") :
# In[266]:
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)
# ## Exercice 7 : `pairs`
#
# C'est un filtrage par le prédicat `x % 2 == 0`.
# Autant écrire la fonction de filtrage générique :
# In[268]:
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)
# Et donc c'est rapide :
# In[269]:
def pairs(liste: ListeChainee) -> ListeChainee:
def predicate(x):
return (x % 2) == 0
# aussi : predicate = lambda x: (x % 2) == 0
return filtrer(liste, predicate)
# In[270]:
def impairs(liste: ListeChainee) -> ListeChainee:
def predicate(x):
return (x % 2) == 1
return filtrer(liste, predicate)
# In[206]:
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]
# In[272]:
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]
# ## Exercice 8 : `range`
#
# Ce sera de complexité temporelle linéaire :
# In[288]:
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))
# In[289]:
print(myrange(1)) # [1]
print(myrange(2)) # [1, 2]
print(myrange(3)) # [1, 2, 3]
print(myrange(4)) # [1, 2, 3, 4]
# 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` :
# In[216]:
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))
# In[217]:
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)) # []
# Une autre approche est d'écrire la fonction `mymap` et de dire que
# ```python
# intervale_bis(a, b) = miroir(mymap(lambda x: x + (a - 1), myrange(b - a + 1)))
# ```
# In[277]:
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))
# In[281]:
print(myrange(10))
print(mymap(lambda x: x, myrange(10)))
# In[290]:
def intervale_bis(a: int, b: int) -> ListeChainee:
return miroir(mymap(lambda x: x + (a - 1), myrange(b - a + 1)))
# In[291]:
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)) # []
# ## 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.
# In[293]:
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
# In[294]:
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))
# In[295]:
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)) # []
# Une version purement fonctionnelle est moins facile qu'une version impérative avec une référence booléenne.
# In[296]:
def estDivisible(n: int, k: int) -> bool:
return (n % k) == 0
# In[236]:
estDivisible(10, 2)
estDivisible(10, 3)
estDivisible(10, 4)
estDivisible(10, 5)
# On est prêt à écrire `estPremier` :
# In[247]:
def estPremier(n : int) -> bool:
return taille(filtrer(intervale2(2, racine(n), 1), lambda k: estDivisible(n, k))) == 0
# 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.
# In[254]:
for n in range(2, 20):
print("Petits diviseurs de", n, " -> ", filtrer(intervale2(2, racine(n), 1), lambda k: estDivisible(n, k)))
# 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.
# In[249]:
def premiers(n : int) -> ListeChainee:
return filtrer(intervale2(2, n, 1), estPremier)
# In[250]:
premiers(10) # [2, 3, 5, 7]
# In[251]:
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]
# ----
# # Quelques tris par comparaison
# On fera les tris en ordre croissant.
# In[112]:
test = [3, 1, 8, 4, 5, 6, 1, 2]
# ## Exercice 10 : Tri insertion
# In[113]:
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)
# In[114]:
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))
# In[115]:
tri_insertion(test)
# Complexité en temps $\mathcal{O}(n^2)$.
# ## Exercice 11 : Tri insertion générique
# In[121]:
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)
# In[122]:
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))
# In[123]:
ordre_croissant = lambda x, y: x <= y
# In[124]:
tri_insertion2(ordre_croissant, test)
# In[125]:
ordre_decroissant = lambda x, y: x >= y
# In[126]:
tri_insertion2(ordre_decroissant, test)
# ## Exercice 12 : Tri selection
# In[127]:
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)
# In[129]:
test
selectionne_min(test)
# (On voit que la liste `autre` a été inversée)
# In[130]:
def tri_selection(liste : List[_a]) -> List[_a]:
if len(liste) == 0:
return []
else:
mini, autres = selectionne_min(liste)
return [mini] + tri_selection(autres)
# In[131]:
tri_selection(test)
# Complexité en temps : $\mathcal{O}(n^2)$.
# ## Exercices 13, 14, 15 : Tri fusion
# In[132]:
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)
# In[133]:
test
separe(test)
# In[134]:
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])
# In[136]:
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))
# In[137]:
tri_fusion(test)
# Complexité en temps $\mathcal{O}(n \log n)$.
# ## Comparaisons
# In[138]:
get_ipython().run_line_magic('timeit', 'tri_insertion(test)')
get_ipython().run_line_magic('timeit', 'tri_selection(test)')
get_ipython().run_line_magic('timeit', 'tri_fusion(test)')
# In[152]:
from sys import setrecursionlimit
setrecursionlimit(100000)
# nécessaire pour tester les différentes fonctions récursives sur de grosses listes
# In[153]:
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__))
get_ipython().run_line_magic('timeit', 'tri(test_random(n))')
# - 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érieur
#
# Je ne corrige pas les questions qui étaient traitées dans le TP1.
# ## Exercice 16 : `applique`
# In[155]:
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
# ## Exercice 17
# In[156]:
def premiers_carres_parfaits(n : int) -> List[int]:
return applique(lambda x : x * x, list(range(1, n + 1)))
# In[157]:
premiers_carres_parfaits(12)
# ## Exercice 18 : `itere`
# In[158]:
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)
# ## Exercice 19
# In[161]:
print_int = lambda i: print("{}".format(i))
# In[163]:
def affiche_liste_entiers(liste : List[int]) -> None:
print("Debut")
itere(print_int, liste)
print("Fin")
affiche_liste_entiers([1, 2, 4, 5, 12011993])
# ## Exercice 20 : `qqsoit` et `ilexiste`
# In[164]:
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
# In[176]:
# 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
# In[177]:
qqsoit(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
ilexiste(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
# In[167]:
get_ipython().run_line_magic('timeit', 'qqsoit(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])')
get_ipython().run_line_magic('timeit', 'all(map(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5]))')
# In[168]:
get_ipython().run_line_magic('timeit', 'ilexiste(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])')
get_ipython().run_line_magic('timeit', 'any(map(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5]))')
# ## Exercice 21 : `appartient` version 2
# In[178]:
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)
# In[179]:
def toutes_egales(x : _a, liste : List[_a]) -> bool:
return qqsoit(lambda y: x == y, liste)
# In[181]:
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])
# 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 !
# In[183]:
get_ipython().run_line_magic('timeit', 'appartient(random.randint(-10, 10), [random.randint(-1000, 1000) for _ in range(1000)])')
get_ipython().run_line_magic('timeit', 'random.randint(-10, 10) in [random.randint(-1000, 1000) for _ in range(1000)]')
# ## Exercice 22 : `filtre`
# In[186]:
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
# In[185]:
filtre(lambda x: (x % 2) == 0, [1, 2, 3, 4, 5])
filtre(lambda x: (x % 2) != 0, [1, 2, 3, 4, 5])
# ## Exercice 23
# Je vous laisse trouver pour `premiers`.
# In[189]:
pairs = lambda liste: filtre(lambda x: (x % 2) == 0, liste)
impairs = lambda liste: filtre(lambda x: (x % 2) != 0, liste)
# In[188]:
pairs(list(range(10)))
impairs(list(range(10)))
# ## Exercice 24 : `reduit`
# In[211]:
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
# Très pratique pour calculer des sommes, notamment.
# ## Exercice 25 : `somme`, `produit`
# In[212]:
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)))
# In[213]:
get_ipython().run_line_magic('timeit', 'somme_rec(list(range(10)))')
get_ipython().run_line_magic('timeit', 'somme(list(range(10)))')
get_ipython().run_line_magic('timeit', 'sum(list(range(10)))')
# Pour de petites listes, la version récursive est aussi efficace que la version impérative. Chouette !
# In[214]:
get_ipython().run_line_magic('timeit', 'somme_rec(list(range(1000)))')
get_ipython().run_line_magic('timeit', 'somme(list(range(1000)))')
get_ipython().run_line_magic('timeit', 'sum(list(range(1000)))')
# In[205]:
from operator import mul
produit = lambda liste: reduit(mul, 1, liste)
produit(list(range(1, 6))) # 5! = 120
# Bonus :
# In[208]:
def factorielle(n : int) -> int:
return produit(range(1, n + 1))
for n in range(1, 15):
print("{:>7}! = {:>13}".format(n, factorielle(n)))
# ## Exercice 26 : `miroir` version 2
# In[220]:
miroir = lambda liste: reduit(lambda l, x : [x] + l, [], liste)
# In[221]:
miroir([2, 3, 5, 7, 11])
# **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
# In[1]:
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]]]
# In[37]:
from pprint import pprint
# In[38]:
arbre_test = {'Noeud': (
{'Noeud': (
{'Noeud': (
{'Feuille': None},
{'Feuille': None}
)},
{'Feuille': None}
)},
{'Feuille': None}
)}
# In[39]:
pprint(arbre_test)
# Avec une syntaxe améliorée, on se rapproche de très près de la syntaxe de Caml/OCaml :
# In[40]:
Feuille = {'Feuille': None}
Noeud = lambda x, y : {'Noeud': (x, y)}
# In[34]:
arbre_test = Noeud(Noeud(Noeud(Feuille, Feuille), Feuille), Feuille)
# In[36]:
pprint(arbre_test)
# ## Exercice 28
# Compte le nombre de feuilles et de sommets.
# In[5]:
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)
# In[6]:
taille(arbre_test) # 7
# ## Exercice 29
# In[7]:
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))
# In[8]:
hauteur(arbre_test) # 3
# ## 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
# In[9]:
from typing import TypeVar, Union, List
F = TypeVar('F')
N = TypeVar('N')
element_parcours = Union[F, N]
parcours = List[element_parcours]
# ## Exercice 32 : Parcours naifs (complexité quadratique)
# In[10]:
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)
# In[11]:
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)
# In[12]:
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)
# 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éaires
#
# On ajoute une fonction auxiliaire et un argument `vus` qui est une liste qui stocke les élements observés dans l'ordre du parcours
# In[13]:
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)
# In[14]:
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)
# In[15]:
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)
# ## 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.html#collections.deque).
# In[16]:
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)
# En remplaçant la file par une pile (une simple `list`), on obtient le parcours en profondeur, avec la même complexité.
# In[17]:
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)
# ## Exercice 35 et fin
# ### Reconstruction depuis le parcours prefixe
# In[18]:
test_prefixe = parcours_prefixe2(arbre_test)
test_prefixe
# 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 commence
# par F et l'arbre doit être une feuille; soit il est de la forme N::q
# où q n'est plus un parcours prefixe mais la concaténation de DEUX parcours
# prefixe, on ne peut donc plus appeler la fonction sur q.
# On va donc écrire une fonction qui prend une liste qui contient plusieurs
# parcours concaténé et qui renvoie l'arbre correspondant au premier parcours
# et ce qui n'a pas été utilisé :
# In[22]:
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")
# In[23]:
reconstruit_prefixe([F])
# In[24]:
reconstruit_prefixe(test_prefixe)
# Et cet exemple va échouer :
# In[25]:
reconstruit_prefixe([N, F, F] + test_prefixe) # échoue
# ### 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 file
# pour stocker les arbres qu'on reconstruit peu à peu depuis les feuilles. La file
# permet de récupérer les bons sous-arbres quand on rencontre un noeud
# In[27]:
largeur_test = parcours_largeur(arbre_test)
largeur_test
# In[41]:
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")
# In[43]:
largeur_test
reconstruit_largeur(largeur_test)
arbre_test
# 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.
# In[44]:
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")
# In[45]:
prefixe_test = parcours_prefixe2(arbre_test)
prefixe_test
# In[46]:
reconstruit_prefixe2(prefixe_test)
arbre_test
# ----
# # Conclusion
#
# Fin. À la séance prochaine.