Apprendre comment implémenter le développement d'un produit de facteurs en Python

Un billet blog de Denis Hulo

En se basant sur le produit cartésien de 2 ensembles, on souhaite réaliser le développement d'un produit de facteurs en Python. C'est-à-dire implémenter une fonction qui pourra transformer un produit de facteurs représenté par une liste de tuples, en une somme réduite de termes représentée par un tuple de tuples.

L'objectif sera d'écrire son propre code, sans utiliser d'autres modules pour Python.


I. Développement du produit de 2 facteurs


I-A. Définition

La multiplication est distributive par rapport à l'addition, cette propriété peut se traduire par :

(a + b) × (c + d) = ac + ad + bc + bd


I-B. Développement du produit de 2 facteurs et produit cartésien

Considérons le produit :

(2a + b) × (a + 3b) = 2aa + 6ab + ba + 3bb

Après réduction de la somme des termes :

(2a + b) × (a + 3b) = 2aa + 7ab + 3bb

On voit que l'on a cette fois besoin de gérer les coefficients des variables pour pouvoir réduire la somme des termes.

Par exemple, le terme 2a sera représenté par le n-uplet (2,a), et le terme 2aa par (2,(a,a)).

Pour simplifier les choses on ne représentera l'exposant des variables que pour afficher le résultat à la fin.

605939

En notant :

f1=(2a + b)
f2=(a + 3b)

Ces 2 facteurs peuvent être représentés par les 2 ensembles :

F1 = {(2,a), (1,b)}
F2 = {(1,a), (3,b)}

Le développement du produit :

p2 = f1 × f2 = (2a + b) × (a + 3b)

nous donne :

p2 = 2aa + 6ab + ba + 3bb

De la même façon, le produit cartésien des 2 ensembles :

E2 = F1 × F2 = {(2,a), (1,b)} × {(1,a), (3,b)}

peut également s'écrire :

E2 = {(2,(a,a)), (6,(a,b)), (1,(b,a)), (3,(b,b))}


Si maintenant on souhaite simplifier l'expression :

p2 = 2aa + 6ab + ba + 3bb

On obtient après regroupement des variables :

p2= 2aa + 7ab + 3bb

On peut de la même façon regrouper les éléments du produit cartésien précédent, pour obtenir l'ensemble :

R (E2) = {(2,(a,a)), (7,(a,b)), (3,(b,b))}

R (E2) représente l'ensemble résultat du regroupement des éléments de E2.


I-C. Implémentation en Python

La fonction developper_produit réalise le produit cartésien entre 2 tuples, puis regroupe les éléments de la liste obtenue. Ces 2 tuples contiennent d'autres tuples représentant les termes des facteurs :

def developper_produit(facteur1,facteur2):
result=[] # initilisation de la liste result
for terme1 in facteur1: # parcours des termes de facteur1 : (a+b) -> [(1,a),(1,b)]
for terme2 in facteur2: # parcours des termes de facteur2 : (c+d) -> [(1,c),(1,d)]
coef = terme1 * terme2 # produit des coefficients des 2 termes : (1,'a') et (1,'c') -> coef = 1*1
var = terme1 + tuple(terme2); var = tuple(sorted(var)) # concaténation des variables : (1,'a') et (1,'c') -> (1,('a','c'))
result = result + [(coef,var)] # ajoute du tuple (coef,var) à la liste result
result = reduire_somme(result) # on réduit la liste des termes, résultat du développement du produit
return result # renvoie la liste result


Pour réduire la liste des termes obtenue, on aura besoin d'une 2e fonction appelée dans la fonction précédente :

def reduire_somme(liste_termes1):
variables = set([terme for terme in liste_termes1]) # on construit la liste des variables
liste_termes2=[] # on initialise la nouvelle liste des termes
for var in variables: # on parcourt la liste des variables
terme = (sum([term for term in liste_termes1 if term==var]),var) # on crée le tuple (sum(coef),var) en regroupant les variables identiques
if terme!=0: # si le coefficient du terme n'est pas égal à 0
liste_termes2 = liste_termes2 + # on ajoute le tuple (sum(coef),var) à la nouvelle liste de termes

def get_second(elem):
return elem


II. Généralisation à plus de deux facteurs


II-A. Définition

La multiplication est dite associative, cette propriété peut se traduire par :

(a + b) × (c + d) × (e + f) = ((a + b) × (c + d)) × (e + f)
(a + b) × (c + d) × (e + f) = (ac + ad + bc + bd) × (e + f)


II-B. Développement du produit de 3 facteurs et produit cartésien

Considérons le produit de 3 facteurs :

(2a + b) × (a + 3b) × (a + 2b) = ((2a + b) × (a + 3b)) × (a + 2b)
(2a + b) × (a + 3b) × (a + 2b) = (2aa + 7ab + 3bb) × (a + 2b)

On va donc utiliser le résultat de notre produit de 2 facteurs (2aa + 7ab + 3bb) pour développer notre produit de 3 facteurs :

605940

En notant :

f1=(2a + b)
f2=(a + 3b)
f3=(a + 2b)

Les 3 facteurs peuvent être représentés par les 3 ensembles :

F1 = {(2,a), (1,b)}
F2 = {(1,a), (3,b)}
F3 = {(1,a), (2,b)}

Le produit des 3 facteurs :

p3 = (f1 × f2) × f3 = ((2a + b) × (a + 3b)) × (a + 2b)
p3 = (2aa + 7ab + 3bb) × (a + 2b)

peut alors être représenté par :

E3 = R (F1 × F2) × F3 = {(2,(a,a)), (7,(a,b)), (3,(b,b))} × {(1,a), (2,b)}

R (F1 × F2) représente l'ensemble résultat du regroupement des éléments de E2 = F1 × F2.


Finalement, on regroupera les éléments de l'ensemble E3, pour obtenir :

R (E3) = {(2,(a,a,a)), (11,(a,a,b)), (17,(a,b,b)), (6,(b,b,b))}


Note importante : Si vous devez développer un produit de plus de 2 facteurs, il est important de regrouper les variables après chaque développement d'un produit de 2 facteurs.

Imaginez d'avoir à développer le produit (a + b)20, si vous choisissez de réduire la somme des termes à la fin, vous aurez à générer avant 220 termes, alors que son développement final après simplification ne contient en réalité que 21 termes.


II-C. Implémentation en Python

Dans le précédent billet produit cartésien, nous avons pu utiliser la fonction produit_cartesien à l'intérieur d'une boucle, pour réaliser le produit de plusieurs itérables.

De la même façon, on va utiliser la fonction developper_produit pour développer un produit de facteurs représenté par une liste de tuples :

for facteur in liste_facteurs: # on parcours les éléments (les facteurs) de la liste
# on développe le produit des 2 facteurs, en réalisant le produit cartésien des 2 tuples, puis le regroupement des éléments de la liste obtenue
result = developper_produit(result,facteur)

Au départ, la variable result ne contient qu'un seul tuple : resultat=[(1,())].

Un tuple vide en Python est noté ().

La fonction developper utilise ce code pour développer un produit de facteurs.

Elle prend comme arguments :

• facteurs : contient la liste des facteurs passée en arguments : [((1,'a'), (1,'b')), ((1,'c'), (1,'d'))] pour (a + b) × (c + d) ;
  
• exposant : ce paramètre optionnel permet de répéter la liste de facteurs. Il revient à élever à la puissance le produit de facteurs.
  

La fonction renvoie un tuple de tuples qui représente en fait une somme de termes. Cette somme pourra ainsi être utilisée comme facteur pour un autre produit.

def developper(facteurs,exposant=1):
liste_facteurs = facteurs*exposant # on construit la liste de facteurs en répétant la liste de départ : [((1,'a'),(1,'b'))]*2 = [((1,'a'),(1,'b')),((1,'a'),(1,'b'))]
result = [(1,())] # on initialise la liste result avec un seul tuple (1,())

for facteur in liste_facteurs: # on parcourt les éléments (les facteurs) de la liste
# on développe le produit des 2 facteurs, en réalisant le produit cartésien des 2 tuples, puis le regroupement des éléments de la liste obtenue
result = developper_produit(result,facteur)

return tuple(result) # on renvoi le résultat du développement sous forme de tuple



II-C-1. Mise en œuvre de la fonction

Prenons par exemple le développement de (a + b)6.

Pour le réaliser, on peut utiliser notre fonction de différentes manières.

1re méthode, on évalue directement (a + b)6 :

resultat=developper([((1,'a'),(1,'b'))],exposant=6)
print(resultat)

2e méthode, on évalue d'abord p3 = (a + b)3, puis (p3)2 :

resultat=developper([((1,'a'),(1,'b'))],exposant=3)
resultat=developper(,exposant=2)
print(expression_somme(resultat))

Affichage :

a^6 + 6a^5b + 15a^4b^2 + 20a^3b^3 + 15a^2b^4 + 6ab^5 + b^6

On utilise la fonction expression_somme pour afficher l'expression mathématique de la somme.

Note : Si on souhaite par exemple développer le produit de facteurs (2 + 3a) × (3 - 2b), on passera à la fonction la liste de tuples [((2,()), (3,'a')), ((3,()), (-2,'b'))].

Module complet pour les tests :

def developper_produit(facteur1,facteur2):
result=[] # initilisation de la liste result
for terme1 in facteur1: # parcours des termes de facteur1 : (a+b) -> ((1,a),(1,b))
for terme2 in facteur2: # parcours des termes de facteur2 : (c+d) -> ((1,c),(1,d))
coef = terme1 * terme2 # produit des coefficients des 2 termes : (1,'a') et (1,'c') -> coef = 1*1
var = terme1 + tuple(terme2); var = tuple(sorted(var)) # concaténation des variables : (1,'a') et (1,'c') -> (1,('a','c'))
result = result + [(coef,var)] # ajoute du tuple (coef,var) à la liste result
result = reduire_somme(result) # on réduit la liste des termes, résultat du développement du produit
return result # renvoie la liste result

def get_first(elem):
return elem

def get_second(elem):
return elem

def reduire_somme(liste_termes1):
variables = set([terme for terme in liste_termes1]) # on construit la liste des variables
liste_termes2=[] # on initialise la nouvelle liste des termes
for var in variables: # on parcourt la liste des variables
terme = (sum([term for term in liste_termes1 if term==var]),var) # on crée le tuple (sum(coef),var) en regroupant les variables identiques
if terme!=0: # si le coefficient du terme n'est pas égal à 0
liste_termes2 = liste_termes2 + # on ajoute le tuple (sum(coef),var) à la nouvelle liste de termes

liste_termes2.sort(key=get_second) # on trie la liste des termes en fonction des variables (seconde colonne : indice 1) pour permettre les regroupements.

return liste_termes2 # on retourne la liste des termes réduite

def developper(facteurs,exposant=1):
liste_facteurs = facteurs*exposant # on construit la liste de facteurs en répétant la liste de départ : [((1,'a'),(1,'b'))]*2 = [((1,'a'),(1,'b')),((1,'a'),(1,'b'))]
result = [(1,())] # on initialise la liste result avec un seul tuple (1,())

for facteur in liste_facteurs: # on parcourt les éléments (les facteurs) de la liste
# on développe le produit des 2 facteurs, en réalisant le produit cartésien des 2 tuples, puis le regroupement des éléments de la liste obtenue
result = developper_produit(result,facteur)

return tuple(result) # on renvoi le résultat du développement sous forme de tuple

def reduire_var(liste_variables1):
variables = set(liste_variables1)
liste_variables2=[] # on initialise la liste des variables
for var in variables: # on parcourt les variables
liste_variables2 = liste_variables2 + [(var,liste_variables1.count(var))] # on ajoute le tuple à la liste : (var, exposant) -> [.., (var, exposant)]
liste_variables2.sort(key=get_first) # on trie la liste des variables
return tuple(liste_variables2)

sign = lambda x : "+" if (x > 0) else "-"

def expression_somme(liste_termes):
expr_som='' # on initialise la chaîne de caractères

for terme in liste_termes: # on parcourt la liste des termes de la somme
liste_variables = reduire_var(terme) # on regroupe la liste des variables du terme en ajoutant leur exposant : ('a','a','a','b') -> (('a',3),('b',1))
expr_var='' # on initialise la chaîne de caractères
for var in liste_variables: # on parcourt la liste des variables du terme
if var==1: # si l'exposant de la variale est égal à 1
expr_var = expr_var + str(var) # on ajoute uniquement la variable à la chaîne
else: # sinon
expr_var = expr_var + str(var) + '^' + str(var) # on ajoute la variable et son exposant à la chaîne

if abs(terme)==1: # si le coefficient du terme est égal à 1 ou -1
expr_som = expr_som + ' ' + sign(terme) + ' ' + expr_var # on ajoute uniquement les variables du terme sans son coefficient
else: # sinon
expr_som = expr_som + ' ' + sign(terme) + ' ' + str(abs(terme)) + expr_var # on ajoute le terme complet à la chaîne

# on renvoie la chaîne contenant l'expression de la somme obtenue moins les 3 premiers caractères (' - ') ou (' + ')
return expr_som[3:] if expr_som[:3]==' + ' else '-' + expr_som[3:]


III. Conclusion

Après avoir représenté le développement du produit de 2 facteurs à l'aide du produit cartésien de 2 ensembles, nous avons pu le généraliser à plus de 2 facteurs, pour enfin l'implémenter en Python.

Sources :
https://fr.wikipedia.org/wiki/Produit_cart%C3%A9sien#:~:text=En%20math%C3%A9matiques%2C%20le%20produit%20cart%C3%A9sien,et%20la%20seconde%20%C3%A0%20Y.
https://python.developpez.com/cours/DiveIntoPython/php/frdiveintopython/toc/index.php