Explication de l'algorithme dans le cas où il y a 3 ensembles A, B et C :
Le but est de récupérer tous les éléments des tuples (x, y, z) tels que :
- x appartient à A,
- y appartient à B,
- z appartient à C et
- x <= y <= z.
Pour cela, l'algorithme ne cherche pas directement les tuples (x, y, z). Il fait quelque chose de plus performant :
- Chercher min_A, le plus petit élément dans A.
- Chercher min_B, le plus petit élément >= min_A dans B.
- Chercher min_C, le plus petit élément >= min_B dans C.
- Si l'une des étapes précédentes échoue, retourner un résultat vide.
- Chercher max_C, le plus grand élément dans C.
- Chercher max_B, le plus grand élément <= max_C dans B.
- Chercher max_A, le plus grand élément <= max_B dans A.
- Récupérer :
- les éléments de A dans [min_A, max_A],
- les éléments de B dans [min_B, max_B] et
- les éléments de C dans [min_C, max_C].
Le vrai algorithme fonctionne pour un nombre quelconque d'ensembles.
Partager