Définition et notations :
Une partition d'un ensemble E est un ensemble P de parties de E non vides et
deux à deux disjointes.
Càd P={X0,...,Xm},
E=⋓i∈[1..m] Xi,
∀i∈[1..m] Xi,
et ∀i≠j∈[1..m] Xi≠Xj.
La finesse d'une partition est définie par le nombre de parties dans la
partition.
schéma algorithmique FUSIONNER Donnée : un ensemble E de taille n. une série de critères de
fusion de parties (F1,...,F1). Résultat : une suite de partitions P de moins en moins fines.
P[0]← ∅ Pourchaque x∈E faire
P← P+{{x}};
Pour i de 1 à m faire
P[i]← P[i−1]; Tantque il existe deux éléments X et Y de P tels que
Fi(X,Y)=Vrai faire
Fusionner X et Y (en X∪Y) dans P[i].
Complexité : en O(m+n) si on considère que chaque test
Fi et chaque fusion X∪Y se font en O(1). (Par complexité
amortie pour les fusions.)
P peut être représenté par un tableau dont les limites de parties sont
matérialisées par une suite d'indices. On conserve le même tableau pour tout
le partitionnement : seule la suite d'indice change d'une partition à
l'autre. N.B. Voir le problème dit UNION-FIND.
schéma algorithmique SEPARER Donnée : un ensemble E de taille n. une série
(F1,...,F1) d'opérations de partition d'un ensemble. Résultat : un suite de partitions de plus en plus fines.
P[0]← E; Pour i de 1 à m faire
P[i]← P[i−1]; Pourchaque X∈P[i] faire
Déterminer Fi(X)={Y,Z} (avec X=Y+Z); Si X≠∅ et Y≠∅ alors
Remplacer X par Y et Z dans P[i].
N.B. On peut construire un arbre des partitions dont P[0]={E}
est la racine et dont les feuilles sont les éléments de la partition la plus
fine.