User

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 = {a₁,a₂}
B = {b₁,b₂,b₃}

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 :

E₂ = A × B
E₂ = {(a₁,b₁),(a₁,b₂),(a₁,b₃),(a₂,b₁),(a₂,b₂),(a₂,b₃)}




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 - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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 = {a₁,a₂}
B = {b₁,b₂,b₃}
C = {c₁,c₂}

Leur produit cartésien s'écrit :

E₃ = A × B × C
E₃ = {a₁,a₂} × {b₁,b₂,b₃} × {c₁,c₂} = ({a₁,a₂} × {b₁,b₂,b₃}) × {c₁,c₂}




II-C. Implémentation en Python

Partons des 3 ensembles A₀, A₁ et A₂, avec :

E₂ = A₀ × A₁
E₃ = A₀ × A₁ × A₂

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 E_i à E_i+1

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

E₀ = {()}

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

Sachant que le produit cartésien de cet ensemble E₀ avec un ensemble quelconque A_i, donne toujours A_i.

On a successivement :

E₁ = A₀ = E₀ × A₀
E₂ = A₀ × A₁ = E₁ × A₁
E₃ = (A₀ × A₁) × A₂ = E₂ × A₂

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

E_i+1 = E_i × A_i avec E₀ = {()}

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

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

A³ = A × A × A
A³ = {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 - Visualiser dans une fenêtre à part

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