Créer des paires (produit cartésien)

Objectif

  • Connaître le fonctionnement d'un produit cartésien.

Mise en situation

Les bases de données sont aujourd'hui très utilisées, et cet usage est largement connu du grand public. Cependant une des opérations de base qui est effectuée sur des bases de données reste très peu connue : le produit cartésien. Cette opération mathématique permet en effet de regrouper deux ensembles de données et de donner la liste des combinaisons possibles entre les éléments de cet ensemble. Nous allons voir que c'est une opération simple à réaliser, mais relativement coûteuse en terme de complexité algorithmique.

Produit cartésien

Le produit cartésien est une opération mathématique entre deux ensembles. Faire le produit cartésien de l'ensemble X avec l'ensemble Y correspond à lister tous les couples possibles entre les éléments de X et ceux de Y. Cette opération est très utilisée dans les bases de données pour créer des relations entre les tables de celle-ci. Voici un exemple pour mieux comprendre cette opération mathématique :

1
persons = {"Jean", "Anne", "Maria"}
2
martialArts = {"Karaté", "Judo"}
3
ProduitCartésien(persons, martialArts) = [
4
 ("Jean", "Karaté"), ("Jean", "Judo"),
5
 ("Anne", "Karaté"), ("Anne", "Judo"),
6
 ("Maria", "Karaté"), ("Maria", "Judo")
7
]

Attention : il ne faut pas lister les couples possibles entre les éléments de X ou de Y confondus.

Par exemple, ("Jean", "Anne") ne fait pas partie du produit cartésien car Jean et Anne font tous les deux partie de X.

MéthodeImplémentation

Pour implémenter, le produit cartésien il faut deux boucles imbriquées. En français, on formulerait l'idée de l'algorithme de la manière suivante : pour chaque élément de X nous créons un couple avec chaque élément de Y.

1
/** JavaScript : Produit cartésien pour obtenir tous les menus possibles. */
2
const vegetables = ['Frites', 'Riz', 'Coquillettes']
3
const sauces = ['Pesto', 'Ketchup']
4
5
for (let i = 0; i < vegetables.length; i = i + 1) {
6
  for (let j = 0; j < sauces.length; j = j + 1) {
7
    console.log(vegetables[i], sauces[j])
8
  }
9
}
10
1
"""Python : Produit cartésien pour obtenir tous les menus possibles. """
2
vegetables = ["Frites", "Riz", "Coquillettes"]
3
sauces = ["Pesto", "Ketchup"]
4
5
for i in range(len(vegetables)):
6
  for j in range(len(sauces)):
7
    print(vegetables[i],sauces[j])
ExempleDéroulement pas à pas
Essayons un déroulement pas à pas avec X = ["Frites", "Riz", "Coquillettes"] et Y = ["Pesto", "Ketchup"].
  • Première itération principale, i = 0 :
    • Première itération secondaire, j = 0 : On affiche « Frites Pesto ».
    • Deuxième itération secondaire, j =1 : On affiche « Frites Ketchup ».
  • Deuxième itération principale, i = 1 :
    • Première itération secondaire, j = 0 : On affiche « Riz Pesto ».
    • Deuxième itération secondaire, j =1 : On affiche « Riz Ketchup ».
  • Troisième itération principale, i = 2 :
    • Première itération secondaire, j = 0 : On affiche « Coquillettes Pesto ».
    • Deuxième itération secondaire, j = 1 : On affiche « Coquillettes Ketchup ».
  • Fin itération principale.
Tous les éléments du produit cartésien ont été affichés.
ComplémentComplexité de produit cartésien
La complexité du produit cartésien est O(n*m). n est le nombre d'éléments de X et m celui de Y. Cette complexité est visible grâce à l’imbrication des boucles.
À retenir
  • Le produit cartésien est une opération mathématique utilisée notamment par les bases de données.
  • Son implémentation est très simple grâce à deux boucles imbriquées.