Combien existe-t-il d'extension totale à un ordre partiel ?

Introduction au problème

Certains ont dû m'entendre poser la question, et même si la formulation mathématique en jette grave elle fait aussi peur. C'est une question que je me pose pour de vrai, et je me suis dit que ce serait intéressant d'en développer la résolution de façon accessible.

Au début je me la posais par rapport à la programmation.
Parfois on utilise des sous-programmes, disons P1 et P2, dans un autre programme, disons P3. Pour aller du plus simple au plus compliqué on a tendance à mettre les sous-programmes avant les programmes, donc P3 sera situé à la fin. Mais il faut quand même choisir si on écrit P1 avant ou après P2.
On a déjà le fait que P1 est avant P3 et que P2 est avant P3 par la dépendance du programme à ses sous-programmes, mais rien n'impose a priori d'écrire P1 avant P2 ou inversement : l'ordre des programmes est partiel. Pourtant le code est sensé être écrit ligne par ligne, donc à la fin tous les programmes sont sensés être ordonnés : l'ordre devrait être total.
Pour l'ordre partiel où P1 et P2 sont avant P3, on a deux façons d'arriver à un ordre total : écrire P1 puis P2 puis P3, ou bien écrire P2 puis P1 puis P3. On a ici deux façons d'étendre l'ordre partiel en un ordre total : en posant P1 avant P2 ou en posant P2 avant P1.

Bien sûr, le problème ne s'applique pas qu'à la programmation et peut être étendu à tout ensemble d'objets qu'il faut organiser. C'est pour ça que le titre est formulé de façon mathématique neutre, et que par la suite j'aurais tendance à nommer les objets par des lettres a, b, c, ... et à noter a < b si a est avant b.


Quelques exemples avant d'attaquer



e utilise c et d, et c utilise a et b.
e pourrait utiliser également a ou b, mais on n'a pas besoin de rajouter de trait : e est avant c qui est avant a, donc dire que e doit être avant a ne rajoute rien. On appelle ce genre de dessin un diagramme de Hasse, et la question revient à se demander de combien de façons différentes on peut aplatir ce genre de graphe.

S'il n'y avait que a, b et c on a vu qu'il y a deux façons : abc et bac.
Comme e doit de toute façon se placer à la fin on n'ajoute pas de nouvelle possibilité en le rajoutant. d n'a pas de contrainte à part être avant e donc peut occuper toutes les positions entre 1 et 4 : ***de, **d*e, *d**e ou d***e, où les trois étoiles correspondent à a, b et c donc doivent être abc ou bac.
Les 2*4 = 8 possibilités sont donc :
abcde (abc et ***de)
bacde (bac et ***de)
abdce (abc et **d*e)
badce (bac et **d*e)
adbce (abc et *d**e)
bdace (bac et *d**e)
dabce (abc et d***e)
dbace (bac et d***e)



Attention, il n'y a pas forcément qu'un seul élément en bas du graphe : rajoutons f qui n'utilise que c. Comme c utilise a et b il est forcément situé au moins à la troisième position. Comme f est après c, il doit être au moins à la quatrième position.
Il y a donc seulement trois possibilités de placer f : ***f**, ****f* ou *****f, où les étoiles représentent les possibilités formées avec a, b, c, d e.
Donc au total il y a 2*4*3 = 24 possibilités.

Conception de l'algorithme

L'idée est d'avoir un moyen récursif de compter le nombre de possibilités nb(G) sur une partie G du graphe.
Le graphe en question peut être supposé connexe (d'un seul tenant), en effet si ce n'était pas le cas on traiterait les différentes parties chacune dans son coin. On peut supposer aussi qu'il n'est pas cyclique (qu'il n'y a pas de boucle), en effet si a utilisait b et que b utilisait a alors on aurait une auto-référence, ce qui est exclu. Avec ces deux propriétés on dit que le graphe est un arbre.
Oh, et bien sûr il n'y a rien à compter si le graphe est vide, s'pas ?

Nous allons donc reconstruire l'arbre point par point en déterminant à chaque étape le nombre de possibilités nb(G) de G selon certaines propriétés de l'arbre partiel G :
- le nombre de points de G : card(G)
- le nombre de points de G situés avant un de ses points y : card(G<y) [1]
- le nombre de points de G situés après un de ses points y : card(G>y) [1]

1) On commence par n'importe quel point x.
Dans ce cas G = {x} et il n'y a qu'une possibilité.

2) On ajoute x dans G en temps que conséquence d'un point y de G :
Dans ce cas x peut être situé n'importe où entre la dernière position et la position juste après la position la plus à gauche possible pour y. Cette position la plus à gauche possible pour y est card(G<y) (le nombre de points avant y, incluant y) en partant de la gauche. Donc x peut occuper les positions 1, 2, ... card({x} U G) - card(G<y) en partant de la droite.
Les card(G) autres positions peuvent être occupées par tous les points de G, ce qui correspond à nb(G) possibilités.
Donc nb({x} U G) = (card({x} U G) - card(G<y))*nb(G)

3) On ajoute x dans G en temps que condition d'un point y de G :
Dans ce cas x peut être situé n'importe où entre la première position et la position juste avant la position la plus à droite possible pour y. Cette position la plus à droite possible pour y est card(G>y) (le nombre de points après y, incluant y) en partant de la droite. Donc x peut occuper les positions 1, 2, ... card({x} U G) - card(G>y) en partant de la gauche.
Les card(G) autres positions peuvent être occupées par tous les points de G, ce qui correspond à nb(G) possibilités.
Donc nb({x} U G) = (card({x} U G) - card(G>y))*nb(G)

On a donc un moyen récursif pour compter le nombre de possibilités. C'est triste parce que ça aurait été mieux d'avoir un moyen plus direct mais je ne suis pas sûr qu'un tel moyen existe...

Application à l'exemple



J'ai renommé les points de façon à choisir un ordre d'évaluation du graphe. Bien sûr il faudrait prouver que l'ordre d'évaluation n'a pas d'importance sur le résultat final, mais je voulais déjà montrer comment faire le calcul.

1) On commence par le point 1.
nb(1) = 1 possibilité

2) On ajoute 2 comme conséquence de 1.
Il y a maintenant deux points au total.
Il y a un point avant 1 (qui est 1 lui-même).
nb(1,2) = (2 - 1)*nb(1) = 1*1 = 1 possibilité

3) On ajoute 3 comme condition de 2.
Il y a maintenant trois points au total.
Il y a un point après 2 (2 lui-même).
nb(1,2,3) = (3 - 1)*nb(1,2) = 2*1 = 2 possibilités

4) On ajoute 4 comme conséquence de 2.
Il y a maintenant quatre points au total.
Il y a trois point avant 2 (qui sont 1, 2 et 3).
nb(1,2,3,4) = (4 - 3)*nb(1,2,3) = 1*2 = 2 possibilités

5) On ajoute 5 comme condition de 4.
Il y a maintenant cinq points au total.
Il y a un point après 4 (4 lui-même).
nb(1,2,3,4,5) = (5 - 1)*nb(1,2,3,4) = 4*2 = 8 possibilités

6) On ajoute 6 comme conséquence de 2.
Il y a maintenant six points au total.
Il y a trois point avant 2 (qui sont 1, 2 et 3).
nb(1,2,3,4,5,6) = (6 - 3)*nb(1,2,3,4,5) = 3*8 = 24 possibilités

-------------------------------------------

[1] G<y est défini par {z dans G ; z <* y}
G>y est défini par {z dans G ; y <* z}
où <* est la clôture réflexive et transitive de <