IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

[Actualité] Produit cartésien en Python

Note : 2 votes pour une moyenne de 5,00.
par , 16/09/2021 à 11h09 (4401 Affichages)
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)}

Nom : produit_cartesien2.png
Affichages : 1921
Taille : 13,1 Ko


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 = {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}

Nom : produit_cartesien3.png
Affichages : 1865
Taille : 35,7 Ko


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 - 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 :

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 - 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

Envoyer le billet « Produit cartésien en Python » dans le blog Viadeo Envoyer le billet « Produit cartésien en Python » dans le blog Twitter Envoyer le billet « Produit cartésien en Python » dans le blog Google Envoyer le billet « Produit cartésien en Python » dans le blog Facebook Envoyer le billet « Produit cartésien en Python » dans le blog Digg Envoyer le billet « Produit cartésien en Python » dans le blog Delicious Envoyer le billet « Produit cartésien en Python » dans le blog MySpace Envoyer le billet « Produit cartésien en Python » dans le blog Yahoo

Commentaires