Ici, pour vous montrer, j'ai utilisé :
beartype.Notez que ce n'est absolument pas nécessaire, c'était juste pour montrer que ce genre d'annotations peut aider à passer de Caml à Python.
def successeur(i : int) -> int:
assert isinstance(i, int), "Erreur : i = {} doit etre entier.".format(i)
assert i >= 0, "Erreur : i = {} doit etre >= 0.".format(i)
return i + 1
successeur(3)
successeur(2 * 2)
successeur(2.5)
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-66-92b9c730a603> in <module> 1 successeur(3) 2 successeur(2 * 2) ----> 3 successeur(2.5) <ipython-input-65-6247174adc0e> in successeur(i) 1 def successeur(i : str) -> float: ----> 2 assert isinstance(i, int), "Erreur : i = {} doit etre entier.".format(i) 3 assert i >= 0, "Erreur : i = {} doit etre >= 0.".format(i) 4 return i + 1 AssertionError: Erreur : i = 2.5 doit etre entier.
def produit3(x, y, z):
return x * y * z
produit3_2 = lambda x, y, z: x * y * z
produit3_3 = lambda x: lambda y: lambda z: x * y * z
produit3(1, 2, 3)
produit3_2(1, 2, 3)
produit3_3(1)(2) # lambda z : 1 * 2 * z
f = produit3_3(1)(2) # lambda z : 1 * 2 * z
f(3)
produit3_3(1)(2)(3)
6
6
<function __main__.<lambda>.<locals>.<lambda>.<locals>.<lambda>(z)>
6
6
def exercice6(n : int) -> None:
for i in range(1, n + 1):
print(i)
for i in range(n, 0, -1):
print(i)
exercice6(4)
1 2 3 4 4 3 2 1
C'est simple. Pas besoin d'un mot clé rec quand on définit une fonction récursive en Python.
def factorielle(n : int) -> int:
if n <= 0:
return 0
elif n == 1:
return 1
else:
return n * factorielle(n - 1)
for i in range(8):
print("{}! = {:>5}".format(i, factorielle(i)))
# Note : ce {:>5} signifie que l'affichage utilise au moins
# 5 caractères, pour avoir un joli alignement :
0! = 0 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040
Pour ce genre de fonction, j'aime bien afficher les appels récursifs. On peut rendre ça optionnel, avec comme ici un argument nommé log, à valeur par défaut log=False.
def pgcd(x : int, y : int, log: bool=False) -> int:
if log: print("x = {:>7}, y = {:>7}".format(x, y))
assert x >= 0 and y >= 0
if y == 1:
return 1
elif y == x or y == 0:
return x
if x < y:
return pgcd(x, y % x, log=log)
else:
return pgcd(y, x % y, log=log)
pgcd(2021, 4, log=True)
x = 2021, y = 4 x = 4, y = 1
1
pgcd(10, 5)
5
On peut faire des essais pour afficher notre calcul de PGCD, sur des entiers aléatoires entre $1$ et $100$.
Pour se rassurer, on peut chercher dans la bibliothèque standard, à partir de Python 3.6 il y a la fonction math.gcd pour calculer le PGCD, sinon fractions.gcd ou encore dans le module (non standard) SymPy sympy.gcd.
try:
from math import gcd
except ImportError:
try:
from fractions import gcd
except ImportError:
from sympy import gcd
from random import randint
for _ in range(10):
x = randint(1, 100)
y = randint(1, 100)
d = pgcd(x, y)
print("{:>3} ^ {:>3} = {:>3}".format(x, y, d))
assert d == gcd(x, y), "Erreur : mauvais calcul de pgcd(x={}, y={}) = {}, alors qu'il devrait etre = {}.".format(x, y, pgcd(x, y), gcd(x, y))
61 ^ 61 = 61 44 ^ 85 = 1 48 ^ 79 = 1 84 ^ 83 = 1 17 ^ 20 = 1 39 ^ 2 = 1 30 ^ 68 = 2 14 ^ 87 = 1 46 ^ 63 = 1 83 ^ 84 = 1
Rien de particulier à faire, la récursivité fonctionne sans réfléchir :
def fibonacci(n : int) -> int:
assert n >= 0
if n == 0 or n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
Dans IPython (ou Jupyter) on peut facilement mesurer le temps (moyen) d'exécution d'une fonction sur une entrée donnée, avec la macro %timeit.
%timeit fibonacci(35)
4.92 s ± 90.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
Dans Python, on peut faire pareil avec timeit() du module timeit.
globals=globals() (globals() donne un dictionnaire qui stocke la valeur de toutes les variables définies, donc ici notamment de fibonacci())number qui par défaut vaut 1000000 : c'est très grand, et donc valable seulement pour estimer le temps de calculs très rapides, par exemple :%timeit 2**35
from timeit import timeit
timeit("2**35") / 1000000
17.3 ns ± 0.152 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
1.744021200283896e-08
from timeit import timeit
number = 5
temps_calcul_fibo35 = timeit("fibonacci(35)", globals=globals(), number=number) / number
print("Pour calculer fibonacci(35), la fonction récursive naïve a pris {} secondes (moyenne sur {} essais)".format(temps_calcul_fibo35, number))
Pour calculer fibonacci(35), la fonction récursive naïve a pris 5.549288985988824 secondes (moyenne sur 1 essais)
Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$.
def fibonacci_lin(n : int) -> int:
fim1, fi = 1, 1
for _ in range(n):
fim1, fi = fi, fim1 + fi
return fim1
On peut vérifier que cette deuxième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide.
for i in range(10):
assert fibonacci(i) == fibonacci_lin(i)
%timeit fibonacci_lin(35)
2.54 µs ± 169 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Pour la version qui est en complexité (temporelle) linéaire dans l'entrée $n$, il suffit de déplier la récursion en calculant $F_{n+1}$ progressivement en partant de $F_0, F_1$.
def fibonacci_lin_rec(n: int) -> int:
# invariant :
# m >= 1
# u = fibo(n-m+1)
# v = fibo(n-m)
# aux m u v = fibo(n)
def aux(m: int, u: int, v: int) -> int:
assert m >= 0
if m <= 1:
return u
else:
return aux(m-1, u+v, u)
return aux(n, 1, 1)
On peut vérifier que cette troisième implémentation fonctionne comme la première, et ensuite vérifier qu'elle est (bien) plus rapide.
for i in range(10):
assert fibonacci(i) == fibonacci_lin_rec(i)
%timeit fibonacci_lin_rec(35)
9.52 µs ± 854 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
Voilà les différences :
import numpy as np
import matplotlib.pyplot as plt
# optionnel : vous ne l'aurez pas le jour de l'oral, mais c'est joli
from tqdm.notebook import tqdm
valeurs_n = np.array(range(1, 32))
number = 5
%%time
temps_calcul_fibo_rec = [
timeit("fibonacci({})".format(n), globals=globals(), number=number) / number
for n in tqdm(valeurs_n)
# enrober un itérateur de la fonction tqdm(...)
# permet d'avoir une joli barre de progression
]
CPU times: user 9.91 s, sys: 3.99 ms, total: 9.91 s Wall time: 9.92 s
number = 100
temps_calcul_fibo_lin = [
timeit("fibonacci_lin({})".format(n), globals=globals(), number=number) / number
for n in tqdm(valeurs_n)
]
temps_calcul_fibo_lin_rec = [
timeit("fibonacci_lin_rec({})".format(n), globals=globals(), number=number) / number
for n in tqdm(valeurs_n)
]
plt.figure(figsize=(14, 10))
plt.plot(valeurs_n, temps_calcul_fibo_rec, "ro-", label="Récursive naïve")
plt.plot(valeurs_n, temps_calcul_fibo_lin, "bd:", label="Linéaire impérative")
plt.plot(valeurs_n, temps_calcul_fibo_lin_rec, "ys:", label="Linéaire récursive")
plt.legend()
plt.title("Comparaison de trois implémentations de la fonction de Fibonacci")
plt.xlabel("Valeurs de n")
plt.ylabel("Temps moyen de calcul en secondes")
plt.show()
%%time
valeurs_n = np.array(range(10, 1000, 10))
number = 1000
temps_calcul_fibo_lin = [
timeit("fibonacci_lin({})".format(n), globals=globals(), number=number) / number
for n in tqdm(valeurs_n)
]
temps_calcul_fibo_lin_rec = [
timeit("fibonacci_lin_rec({})".format(n), globals=globals(), number=number) / number
for n in tqdm(valeurs_n)
]
CPU times: user 22.7 s, sys: 124 ms, total: 22.8 s Wall time: 22.7 s
plt.figure(figsize=(14, 10))
plt.plot(valeurs_n, temps_calcul_fibo_lin, "bd:", label="Linéaire impérative")
plt.plot(valeurs_n, temps_calcul_fibo_lin_rec, "ys:", label="Linéaire récursive")
plt.legend()
plt.title("Comparaison de deux implémentations de la fonction de Fibonacci")
plt.xlabel("Valeurs de n")
plt.ylabel("Temps moyen de calcul en secondes")
plt.show()
Aucune hypothèse n'est faite sur les arguments de la fonction, on supposera seulement qu'elle est itérable sur sa sortie.
from types import FunctionType # inutile, juste pour faire joli
# première version, f : type x -> type x (simple)
def itere(f : FunctionType, n : int) -> FunctionType:
def fn(x):
for _ in range(n):
x = f(x)
return x
return fn
itere(lambda x: x + 1, 10)(1)
11
On peut aussi écrire une version récursive :
def compose(f, g):
return lambda x: f(g(x))
"""
def f_rond_g(x):
return f(g(x))
return f_rond_g
"""
def itere_rec(f : FunctionType, n : int) -> FunctionType:
assert n >= 0
if n == 0:
return lambda x: x
elif n == 1:
return f
else:
return compose(f, itere_rec(f, n-1))
return compose(itere_rec(f, n-1), f)
itere_rec(lambda x: x + 1, 10)(1)
11
%timeit itere(lambda x: x + 1, 1000)(1)
%timeit itere_rec(lambda x: x + 1, 1000)(1)
969 µs ± 89.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 946 µs ± 79.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
# deuxième version, f : tuple -> tuple (simple)
def itere2(f : FunctionType, n : int) -> FunctionType:
def fn(*args):
for _ in range(n):
if isinstance(args, tuple):
args = f(*args)
else:
args = f(args)
if isinstance(args, tuple) and len(args) == 1:
return args[0]
else:
return args
return fn
def plusun(x):
return x + 1
itere2(plusun, 10)(1)
def foisdeux(x, y):
return x * 2, y * 2
itere2(foisdeux, 10)(1, 2)
11
(1024, 2048)
C'est assez naturel, on affiche la suite de mouvement à faire, comme une suite de "T1 -> T2" par exemple.
La fonction suivante affiche les déplacements qu'il faut faire pour déplacer une tour de hauteur n initialement posée en x, à destination de z et avec y comme position intermédiaire.
x vers z suffit,n, il faut déplacer de x vers y le haut de la tour (de hauteur n-1 : 1er appel récursif), puis déplacer le plus gros disque (en un mouvement) de x vers z, puis de nouveau déplacer le haut de la tour (toujours de hauteur n-1 : 2nd appel récursif) de y vers z.def hanoi(x : str, y : str, z : str, n : int) -> None:
def hanoiaux(orig : str, dest : str, inter : str, n : int):
if n == 0:
return 0
c1 = hanoiaux(orig, inter, dest, n - 1)
print("{} -> {}".format(orig, dest))
c2 = hanoiaux(inter, dest, orig, n - 1)
return c1 + 1 + c2
return hanoiaux(x, z, y, n)
hanoi("T1", "T2", "T3", 1)
T1 -> T3
1
hanoi("T1", "T2", "T3", 2)
T1 -> T2 T1 -> T3 T2 -> T3
3
hanoi("T1", "T2", "T3", 5) # 31 = 2^5 - 1
T1 -> T3 T1 -> T2 T3 -> T2 T1 -> T3 T2 -> T1 T2 -> T3 T1 -> T3 T1 -> T2 T3 -> T2 T3 -> T1 T2 -> T1 T3 -> T2 T1 -> T3 T1 -> T2 T3 -> T2 T1 -> T3 T2 -> T1 T2 -> T3 T1 -> T3 T2 -> T1 T3 -> T2 T3 -> T1 T2 -> T1 T2 -> T3 T1 -> T3 T1 -> T2 T3 -> T2 T1 -> T3 T2 -> T1 T2 -> T3 T1 -> T3
31
Les listes en Python sont des list.
Elles ne fonctionnent pas comme des listes simplement chaînées comme en Caml : ce sont des tableaux, donc l'accès à T[i] pour n'importe quel i est en $\mathcal{O}(1)$ pour n'importe quel i et n.
MUST READ Allez lire la page https://wiki.python.org/moin/TimeComplexity#list en détail !
def concatene(liste1 : list, liste2 : list) -> list:
""" O(len(liste1) + len(liste2))"""
# return liste1 + liste2 # solution facile
n1, n2 = len(liste1), len(liste2)
res = []
for i in range(n1 + n2):
if i < n1:
res.append(liste1[i])
else:
res.append(liste2[i - n1])
return res
concatene([1, 2, 3], [4, 5])
[1, 2, 3, 4, 5]
from types import FunctionType
def applique(f : FunctionType, liste : list) -> list:
res = [f(x) for x in liste] # solution facile
res = map(f, liste) # encore plus facile
# en itérant la liste :
res = [ ] # tableau vide
for x in liste:
res.append(f(x))
# en itérant ses valeurs :
res = [ ] # tableau
for i in range(len(liste)):
res.append(f(liste[i]))
return res
applique(lambda x : x + 1, [1, 2, 3])
[2, 3, 4]
def liste_carree(liste : list) -> list:
return applique(lambda x: x**2, liste)
liste_carree([1, 2, 3])
[1, 4, 9]
def miroir_quad(liste : list) -> list:
# aucune idée pour le faire innefficacement en Python,
# ce ne sont pas des listes chaînées
return liste[::-1]
def miroir_lin(liste : list) -> list:
return [liste[-i] for i in range(1, len(liste) + 1)]
miroir_lin([1, 2, 3])
[3, 2, 1]
def insertion_dans_liste_triee(entiers : list, x : int) -> list:
i = 0
while i < len(entiers) and entiers[i] < x:
i += 1
return entiers[:i] + [x] + entiers[i:]
insertion_dans_liste_triee([1, 2, 5, 6], 4)
[1, 2, 4, 5, 6]
def tri_insertion(entiers : list) -> list:
assert all([isinstance(i, int) for _ in entiers])
def trix(e : list, acc : list) -> list:
if len(e) == 0: return acc
else: return trix(e[1:], insertion_dans_liste_triee(acc, e[0]))
return trix(entiers, [])
tri_insertion([5, 2, 6, 1, 4])
[1, 2, 4, 5, 6]
def ordre_decroissant(x, y):
return x > y
from types import FunctionType
def insertion_dans_liste_triee2(entiers : list, x : int, ordre : FunctionType) -> list:
i = 0
while i < len(entiers) and ordre(entiers[i], x):
i += 1
return entiers[:i] + [x] + entiers[i:]
insertion_dans_liste_triee2([6, 5, 2, 1], 4, ordre_decroissant)
[6, 5, 4, 2, 1]
def tri_insertion2(entiers : list, ordre : FunctionType) -> list:
assert all([isinstance(i, int) for _ in entiers])
def trix(e : list, acc : list) -> list:
if len(e) == 0: return acc
else: return trix(e[1:], insertion_dans_liste_triee2(acc, e[0], ordre))
return trix(entiers, [])
tri_insertion([5, 2, 6, 1, 4])
tri_insertion2([5, 2, 6, 1, 4], ordre_decroissant)
[1, 2, 4, 5, 6]
[6, 5, 4, 2, 1]
def exp(x : int, n : int) -> int:
res = 1
for _ in range(n):
res *= x
return res
x = 3
for n in range(8):
print(x, "**", n, "=", exp(x, n), "et =", x**n)
3 ** 0 = 1 et = 1 3 ** 1 = 3 et = 3 3 ** 2 = 9 et = 9 3 ** 3 = 27 et = 27 3 ** 4 = 81 et = 81 3 ** 5 = 243 et = 243 3 ** 6 = 729 et = 729 3 ** 7 = 2187 et = 2187
x = 3
for n in range(8):
print(" {} ** {} = {:>5}".format(x, n, exp(x, n)))
3 ** 0 = 1 3 ** 1 = 3 3 ** 2 = 9 3 ** 3 = 27 3 ** 4 = 81 3 ** 5 = 243 3 ** 6 = 729 3 ** 7 = 2187
Une approche maline (optimale, en fait).
Si n = 0 $x^0 = 1$
Si n est pair : $$ x^n = (x^{(n/2)})^2$$ $$ x^n = (x*x)^{(n/2)}$$
Si n est impair : $$ x^n = x * (x^{((n-1)/2)})^2$$ $$ x^n = x * (x*x)^{((n-1)/2)}$$
def exp2(x : int, n : int) -> int:
assert n >= 0
if n == 0:
return 1
elif n == 1:
return x
elif n % 2 == 0:
# NE PAS FAIRE CA
# return exp2(x, n // 2) * exp2(x, n // 2)
return exp2(x * x, n // 2)
return exp2(x, n // 2) ** 2
elif n % 2 == 1:
return exp2(x * x, (n - 1) // 2) * x
x = 3
for n in range(8):
print(" {} ** {} = {:>5}".format(x, n, exp2(x, n)))
3 ** 0 = 1 3 ** 1 = 3 3 ** 2 = 9 3 ** 3 = 27 3 ** 4 = 81 3 ** 5 = 243 3 ** 6 = 729 3 ** 7 = 2187
x = 3.1415
for n in range(8):
print(" {} ** {} = {:>5} et x**n = {}".format(x, n, exp2(x, n), x**n))
3.1415 ** 0 = 1 et x**n = 1.0 3.1415 ** 1 = 3.1415 et x**n = 3.1415 3.1415 ** 2 = 9.86902225 et x**n = 9.86902225 3.1415 ** 3 = 31.003533398375 et x**n = 31.003533398375005 3.1415 ** 4 = 97.39760017099508 et x**n = 97.39760017099509 3.1415 ** 5 = 305.974560937181 et x**n = 305.9745609371811 3.1415 ** 6 = 961.2190831841542 et x**n = 961.2190831841544 3.1415 ** 7 = 3019.6697498230205 et x**n = 3019.6697498230214
On ne dispose pas de typage pour faire ça aussi joliment qu'en Caml...
def mult_float(x : float, y : float) -> float:
return x * y
monoide_flottants = {
'mult': mult_float, # (*.) en Caml
'neutre': 1.
}
class Monoide_flottant():
def __init__(self, x):
self.x
self.neutre = 1.0
def mult(self, other_float):
return self.x * other_float.x
import numpy as np
def mult_ndarray(A : np.array, B : np.array) -> np.array:
return np.dot(A, B)
# Pas possible d'avoir un neutre pour une taille quelconque !
monoide_nparray = lambda n, m: {
'mult': mult_ndarray,
'neutre': np.eye(n, m)
}
mult_ndarray([[1, 1], [1, 1]], [[1, 2], [3, 4]])
array([[4, 6],
[4, 6]])
Manuellement ce n'est pas trop dur :
def mult_mat(A : list, B : list) -> list:
n, m = len(A), len(A[0]) # A est (n, m)
m2, p = len(B), len(B[0]) # B est (m2, p)
assert m == m2
C = [[0 for _ in range(p)] for _ in range(n)] # C est (n, p)
for i in range(n):
for j in range(p):
for k in range(m):
C[i][j] += A[i][k] * B[k][j]
return C
# Pas possible d'avoir un neutre pour une taille quelconque !
monoide_mat = lambda n, m: {
'mult': mult_mat,
'neutre': [[int(i==j) for j in range(m)] for i in range(n)] # I est (n, m)
}
mult_mat([[1, 1], [1, 1]], [[1, 2], [3, 4]])
[[4, 6], [4, 6]]
def exp_rapide(monoide : dict, x, n : int):
mult = monoide['mult']
assert n >= 0
if n == 0:
return monoide['neutre']
elif n == 1:
return x
elif n % 2 == 0:
return exp_rapide(monoide, mult(x, x), n // 2)
elif n % 2 == 1:
return mult(exp_rapide(monoide, mult(x, x), (n - 1) // 2), x)
def exp_rapide_float(x : float, n : int) -> float:
return exp_rapide(monoide_flottants, x, n)
exp_rapide_float(2.0, 8)
256.0
exp_rapide_float(0.2, 8)
2.560000000000002e-06
Et pour les matrices, un petit piège à cause des tailles :
def exp_rapide_mat(A : list, k : int) -> float:
n, m = len(A), len(A[0])
mono = monoide_mat(n, m)
return exp_rapide(mono, A, k)
for k in range(5):
exp_rapide_mat([[1, 1], [1, 1]], k)
[[1, 0], [0, 1]]
[[1, 1], [1, 1]]
[[2, 2], [2, 2]]
[[4, 4], [4, 4]]
[[8, 8], [8, 8]]
for k in range(5): # nilpotente
exp_rapide_mat([[0, 1, 2], [0, 0, 1], [0, 0, 0]], k)
[[1, 0, 0], [0, 1, 0], [0, 0, 1]]
[[0, 1, 2], [0, 0, 1], [0, 0, 0]]
[[0, 0, 1], [0, 0, 0], [0, 0, 0]]
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
itere :def exp_rapide_2(x, n : int):
def mul_par_x(y):
return x * y
return itere(mul_par_x, n)(x)
exp_rapide_2(2.0, 8)
512.0
itere avec l'exponentiation rapide :def mult_fonction(f : FunctionType, g : FunctionType) -> FunctionType:
return lambda x: f(g(x))
monoide_fonction = {
'mult': mult_fonction,
'neutre': lambda x: x # identité !
}
def itere_depuis_monoide(f, n):
return exp_rapide(monoide_fonction, f, n)
print(itere_depuis_monoide(lambda x: x+1, 0)(1)) # 1
print(itere_depuis_monoide(lambda x: x+1, 10)(1)) # 11
print(itere_depuis_monoide(lambda x: x+1, 1000000)(1)) # pas de stack overflow car complexité O(log(n))
1 11 1000001
A comparer avec l'implémentation naïve qui était en $\mathcal{O}(n)$ :
print(itere(lambda x: x+1, 0)(1)) # 1
print(itere(lambda x: x+1, 10)(1)) # 11
print(itere(lambda x: x+1, 1000000)(1)) # stack overflow car complexité O(n)
1 11
--------------------------------------------------------------------------- RecursionError Traceback (most recent call last) <ipython-input-101-e5141bc75381> in <module> 1 print(itere(lambda x: x+1, 0)(1)) # 1 2 print(itere(lambda x: x+1, 10)(1)) # 11 ----> 3 print(itere(lambda x: x+1, 1000000)(1)) # pas de stack overflow car complexité O(log(n)) <ipython-input-100-4ff528828113> in <lambda>(x) 3 return lambda x: x 4 else: ----> 5 return lambda x: (itere(f, n-1))(f(x)) ... last 1 frames repeated, from the frame below ... <ipython-input-100-4ff528828113> in <lambda>(x) 3 return lambda x: x 4 else: ----> 5 return lambda x: (itere(f, n-1))(f(x)) RecursionError: maximum recursion depth exceeded in comparison
(not p ^ ((q ^ not p) v (r v q))) s'écrit en Caml (Conj(Not(V("p")),Disj(Conj(V("q"),Not(V("p"))),Disj(V("r"),V("q"))))).
On va imbriquer des dictionnaires, les types, V, Not, Conj et Disj seront des clés, et les valeurs seront des formules ou couples de formules.
Mais on va cacher ça et l'utilisateur verra exactement la même chose qu'en Caml !
V = lambda x: {'V': x}
Not = lambda x: {'Not': x}
Disj = lambda x, y: {'Disj': (x, y)}
Conj = lambda x, y: {'Conj': (x, y)}
p = V('p')
r = V('r')
q = V('q')
not_p = Not(p)
f = Conj(Not(p), Disj(Conj(q, not_p), Disj(r, q)))
f
{'Conj': ({'Not': {'V': 'p'}},
{'Disj': ({'Conj': ({'V': 'q'}, {'Not': {'V': 'p'}})},
{'Disj': ({'V': 'r'}, {'V': 'q'})})})}
f2 = (Conj(Not(V("p")),Disj(Conj(V("q"),Not(V("p"))),Disj(V("r"),V("q")))))
f2
{'Conj': ({'Not': {'V': 'p'}},
{'Disj': ({'Conj': ({'V': 'q'}, {'Not': {'V': 'p'}})},
{'Disj': ({'V': 'r'}, {'V': 'q'})})})}
Si on veut afficher plus joliment ce genre de structures récursives, la fonction pprint.pprint(...) est là pour ça (elle affiche avec de l'indentation) :
from pprint import pprint
pprint(f2)
{'Conj': ({'Not': {'V': 'p'}},
{'Disj': ({'Conj': ({'V': 'q'}, {'Not': {'V': 'p'}})},
{'Disj': ({'V': 'r'}, {'V': 'q'})})})}
Ensuite on fait une filtration "à la main" sur les clés du dictionnaire (de niveau 1, on ne récurse pas quand on teste 'V' in formule).
def taille(formule : dict) -> int:
if 'V' in formule:
return 0
elif 'Not' in formule:
return 1 + taille(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return 1 + taille(x) + taille(y)
elif 'Disj' in formule:
x, y = formule['Disj']
return 1 + taille(x) + taille(y)
taille(f)
6
taille(f2)
6
def formule_to_string(formule : dict) -> str:
if 'V' in formule:
return formule['V']
elif 'Not' in formule:
return "~" + formule_to_string(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return "(" + formule_to_string(x) + " ^ " + formule_to_string(y) + ")"
elif 'Disj' in formule:
x, y = formule['Disj']
return "(" + formule_to_string(x) + " V " + formule_to_string(y) + ")"
def affiche(formule):
print(formule_to_string(formule))
affiche(f)
(~p ^ ((q ^ ~p) V (r V q)))
Et voilà. Pas tellement plus dur hein !
Les valeurs des variables seront données comme un dictionnaire associant nom de variable à valeurs booléennes.
Et comme on veut frimer, on prend un defaultdict, qui est comme un dict mais qui stocke aussi une fonction qui donne la valeur des clés absentes du dictionnaire :
from collections import defaultdict
d = defaultdict(lambda: False, {'p': True, 'q': False})
print(d['p']) # -> True car présent et True
print(d['q']) # -> False car présent et False
print(d['x']) # -> False car absent
print(d['xokazeok']) # -> False car absent
True False False False
valeurs_1 = defaultdict(lambda: False, {'p': True})
valeurs_2 = defaultdict(lambda: False, {'r': True})
def eval(valeurs : dict, formule : dict) -> bool:
if 'V' in formule:
return valeurs[formule['V']]
elif 'Not' in formule:
return not eval(valeurs, formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return eval(valeurs, x) and eval(valeurs, y)
elif 'Disj' in formule:
x, y = formule['Disj']
return eval(valeurs, x) or eval(valeurs, y)
eval(valeurs_1, f)
False
eval(valeurs_2, f)
True
def extrait_variables_x(formule : dict) -> list:
if 'V' in formule:
return [formule['V']]
elif 'Not' in formule:
return extrait_variables_x(formule['Not'])
elif 'Conj' in formule:
x, y = formule['Conj']
return extrait_variables_x(x) + extrait_variables_x(y)
elif 'Disj' in formule:
x, y = formule['Disj']
return extrait_variables_x(x) + extrait_variables_x(y)
# on enlève les doublons
def extrait_variables(formule : dict) -> list:
return list(set(extrait_variables_x(formule)))
extrait_variables(f)
['p', 'r', 'q']
On trouve facilement les $n$ variables d'une formule.
Ensuite, un itertools.product permet de générer les $2^n$ valuations.
from itertools import product
def toutes_valeurs(variables):
for valeurs in product([False, True], repeat=len(variables)):
yield defaultdict(lambda: False, {k:v for k,v in zip(variables, valeurs)})
list(toutes_valeurs(extrait_variables(f)))
[defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': False, 'q': False, 'r': False}),
defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': False, 'q': True, 'r': False}),
defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': False, 'q': False, 'r': True}),
defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': False, 'q': True, 'r': True}),
defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': True, 'q': False, 'r': False}),
defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': True, 'q': True, 'r': False}),
defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': True, 'q': False, 'r': True}),
defaultdict(<function __main__.toutes_valeurs.<locals>.<lambda>>,
{'p': True, 'q': True, 'r': True})]
def str_of_bool(x : bool) -> str:
# return str(int(x))
return '1' if x else '0'
def table_verite(formule : dict) -> None:
variables = extrait_variables(formule)
# D'abord la formule
for k in variables:
print(k, end=' ')
print('| ', end='')
affiche(f)
# Puis toutes ces valeurs possibles
for valeurs in toutes_valeurs(variables):
for k in variables:
print(str_of_bool(valeurs[k]), end=' ')
print('| ', end='')
print(str_of_bool(eval(valeurs, formule)))
table_verite(f)
p r q | (~p ^ ((q ^ ~p) V (r V q))) 0 0 0 | 0 0 0 1 | 1 0 1 0 | 1 0 1 1 | 1 1 0 0 | 0 1 0 1 | 0 1 1 0 | 0 1 1 1 | 0
Note : ce code est encore plus concis que celui donné dans la solution en Caml.
On peut vérifier, par exemple sur Wolfram|Alpha que l'on obtient bien le bon résultat...
Comme vous le voyez, on arrive à répondre aux mêmes questions dans les deux langages, et il n'y a pas de grosses différences en pratique dans la mise en oeuvre.
Là où OCaml excelle pour les types définis, le filtrage et la récursion, Python gagne en simplicité sur l'affichage, sa librairie standard et les dictionnaires et ensembles...