Apprendre à implémenter une fonction en Python qui pourra réaliser le produit cartésien de plusieurs itérables,

Un billet blog de Denis Hulo

Après les combinaisons et les arrangements, on s'intéresse maintenant au produit cartésien.

L'objectif sera d'implémenter une fonction en Python qui pourra réaliser le produit cartésien de plusieurs itérables (listes, chaînes de caractères, tuples, etc.).


I. Produit cartésien de 2 ensembles


I-A. Définition

En mathématiques, le produit cartésien de deux ensembles A et B, appelé également ensemble-produit, est l'ensemble de tous les couples dont la première composante appartient à A et la seconde à B.

I-B. Exemple

On considère les 2 ensembles :

A = {a1,a2}
B = {b1,b2,b3}

On souhaite donc obtenir l'ensemble de tous les couples dont la première composante appartient à A et la seconde à B.

Le produit cartésien des 2 ensembles s'écrit :

E2 = A × B
E2 = {(a1,b1),(a1,b2),(a1,b3),(a2,b1),(a2,b2),(a2,b3)}

604799


I-C. Implémentation en Python

En Python, on peut par exemple réaliser le produit cartésien de 2 listes en utilisant 2 boucles imbriquées :

l=[] # initialisation de la liste destinée à contenir le résultat du produit cartésien
for e1 in l1: # parcours des éléments de la 1re liste
for e2 in l2: # parcours des éléments de la 2e liste
l.append((e1,e2)) # on ajoute le tuple à la liste


De la même manière, on peut écrire une fonction permettant de réaliser le produit cartésien de 2 itérables (listes, tuples, chaînes de caractères, etc.) :

def produit_cartesien(iterable1,iterable2):
for e1 in iterable1: # parcours des éléments du 1er itérable
for e2 in iterable2: # parcours des éléments du 2e itérable
yield (e1,e2) # ordre de générer le tuple comportant les éléments de e1 et e2


Nous utilisons l'instruction yield qui permet de générer un grand nombre de tuples sans avoir besoin de les stocker en mémoire.



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


II-A. Définition

Le produit cartésien est dit associatif, et le produit de 3 ensembles :

E = A × B × C

Peut également s'écrire :

E = (A × B) × C

On obtient donc le produit cartésien de (A × B) et C. On peut ainsi facilement le généraliser à plus de 2 ensembles.


II-B. Exemple

Considérons les 3 ensembles :

A = {a1,a2}
B = {b1,b2,b3}
C = {c1,c2}

Leur produit cartésien s'écrit :

E3 = A × B × C
E3 = {a1,a2} × {b1,b2,b3} × {c1,c2} = ({a1,a2} × {b1,b2,b3}) × {c1,c2}

604800


II-C. Implémentation en Python

Partons des 3 ensembles A0, A1 et A2, avec :

E2 = A0 × A1
E3 = A0 × A1 × A2

On fait commencer les indices à 0, comme pour les listes et les tuples en Python.

Pour généraliser le produit cartésien, on va chercher à établir une relation de récurrence pour passer de Ei à Ei+1

On part de l'ensemble E0 ne contenant qu'un seul 0-uplet :

E0 = {()}

Un 0-uplet ou tuple vide en Python est noté ().

Sachant que le produit cartésien de cet ensemble E0 avec un ensemble quelconque Ai, donne toujours Ai.

On a successivement :

E1 = A0 = E0 × A0
E2 = A0 × A1 = E1 × A1
E3 = (A0 × A1) × A2 = E2 × A2

On peut alors identifier une relation de récurrence permettant de passer de Ei à Ei+1 :

Ei+1 = Ei × Ai avec E0 = {()}

Cette dernière relation peut se traduire en Python, à l'aide de la fonction précédente, par :

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

La fonction produit utilise cette instruction pour réaliser le produit cartésien de plusieurs itérables. Elle effectue en fait plusieurs appels à la fonction produit_cartesien dans une boucle.

Elle prend comme arguments :

• *args : contient la liste des itérables passés en arguments ;
  
• repeat : ce paramètre optionnel permet de répéter les itérables.
  

def produit(*args, repeat=1):
iterables = args*repeat # on répète les itérables : ([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],..)
result=[()] # on initialise la variable result avec une liste contenant un seul tuple vide

for it in iterables: # parcours des itérables
result = produit_cartesien(result,it) # produit cartésien entre le résultat du produit précédent et l'itérable courant

return result # on renvoi le résultat du produit des itérables

def produit_cartesien(iterable1,iterable2):
for e1 in iterable1: # parcours des éléments du 1er itérable (liste, tuple ou chaîne de caractères)
for e2 in iterable2: # parcours des éléments du 2e itérable (liste, tuple ou chaîne de caractères)
yield (e1 + (e2,)) # ordre de générer le tuple comportant les éléments de e1 plus l'élément e2

On a légèrement modifié la fonction produit_cartesien pour nous permettre de générer des tuples comportant l'ensemble des éléments de e1 plus l'élément e2 avec l'instruction yield (e1 + (e2,)).

Pour ajouter par exemple un élément 3 à un tuple (1,2), on fait simplement : (1,2) + (3,) = (1,2,3)


Vous trouverez ce type de fonction dans la librairie itertools pour Python.


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

On souhaite générer l'ensemble des triplets composés de 3 chiffres décimaux.

Soit l'ensemble des 10 chiffres décimaux :

A = {0,1,2,3,4,5,6,7,8,9}

On va réaliser le cube de cet ensemble :

A3 = A × A × A
A3 = {0,1,2,3,4,5,6,7,8,9} × {0,1,2,3,4,5,6,7,8,9} × {0,1,2,3,4,5,6,7,8,9}

Ceci étant posé, on peut maintenant utiliser notre fonction produit pour générer l'ensemble des tuples composés de 3 chiffres :

iterateur = produit([0,1,2,3,4,5,6,7,8,9],repeat=3) # appel de la fonction

for e in iterateur: # on génère dans une boucle l'ensemble des tuples résultat du produit cartésien
print(e) # on affiche le tuple e

L'exécution du code affiche la liste des 1000 tuples résultat du produit :

(0, 0, 0)
(0, 0, 1)
(0, 0, 2)
...
(9,9,9)


III. Conclusion

Après avoir défini et donné un exemple de produit cartésien de 2 ensembles, nous avons pu le généraliser à plus de deux ensembles, 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://deusyss.developpez.com/tutoriels/Programmation/introduction_iterateurs_generateurs