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

Vous êtes nouveau sur Developpez.com ? Créez votre compte ou connectez-vous afin de pouvoir participer !

Vous devez avoir un compte Developpez.com et être connecté pour pouvoir participer aux discussions.

Vous n'avez pas encore de compte Developpez.com ? Créez-en un en quelques instants, c'est entièrement gratuit !

Si vous disposez déjà d'un compte et qu'il est bien activé, connectez-vous à l'aide du formulaire ci-dessous.

Identifiez-vous
Identifiant
Mot de passe
Mot de passe oublié ?
Créer un compte

L'inscription est gratuite et ne vous prendra que quelques instants !

Je m'inscris !

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

Le , par User

0PARTAGES

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

Une erreur dans cette actualité ? Signalez-nous-la !