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)}
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 :
| Code Python : | Sélectionner tout |
1 2 3 4 | 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.) :
| Code Python : | Sélectionner tout |
1 2 3 4 | 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}
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 :
| Code Python : | Sélectionner tout |
result = produit_cartesien(result,iterable)
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.
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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 :
| Code Python : | Sélectionner tout |
1 2 3 4 | 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/Produi...%20%C3%A0%20Y.
https://deusyss.developpez.com/tutor...rs_generateurs