classement

Publié le par jö

Cet article fait référence à celui sur le dénombrement. On avait remarqué que le classement suivant les situations les plus probables n'était pas le même que le classement suivant l'équilibrage (qui n'est de toute façon pas défini très clairement) et on va montrer un type de classement avantageux pour l'implémentation en machine.

De manière à programmer séquentiellement le calcul qui donne les s valeurs v_i contenues dans chaque chapitre principal, il est utile de considérer la donnée d'un chapitre comme un s-upplet de dimension s-1 car on a toujours sum( i=1, i=s, v_i ) = j.

Ainsi, en écartant temporairement une des valeurs de chaque chapitre (par exemple la plus grande c'est-à-dire la première dans la présentation), on est amené à chercher une relation d'ordre entre {0,0,0,0}, {1,0,0,0}, {2,0,0,0},...., et {2,2,1,0} et il est maintenant presque immédiat d'observer (il faut pour cela conserver l'ordre décroissant à l'intérieur du chapitre) qu'on peut passer d'un de ces nouveaux chapitres au suivant grâce à quelques règles simples (et ce n'était pas du tout évident au départ) :
  1. la règle basique : on ajoute 1 au terme le plus à gauche.
  2. comme la valeur qu'on a écartée correspond au complément à j de la somme des valeurs de ce nouveau chapitre, il faut s'assurer que le terme à gauche qu'on vient de modifier est toujours inférieur ou égal à ce complément : si c'est le cas la règle 1 est suffisante.
  3. si ce n'est pas le cas, il faut considérer tout d'abord le terme à droite du terme le plus à gauche : on l'incrémente de 1 mais cette fois il faut recopier la valeur obtenue sur le terme le plus à gauche. On contrôle comme avant la condition d'infériorité.
  4. tant que cette condition n'est pas remplie, on considère des termes de plus en plus à droite et on recopie de même leur nouvelle valeur sur les termes à leur gauche.

On peut comprendre ce phénomène de recopie en se rappelant qu'on travaille avec des (s-1)-upplets et non pas des vecteurs ce qui fait que si {4,1,0,0} ne peut pas être le successeur de {3,1,0,0} pour des raisons d'infériorités, le candidat pour le successeur ne peut  être ni {0,2,0,0} ni {1,2,0,0} non plus à cause de l'ordre décroissant à l'intérieur qui garantit l'unicité des chapitres et évite les collisions avec {2,0,0,0} et  {2,1,0,0}.

On détaille donc l'ordre obtenu :

On débute avec {0,0,0,0} ->complémentation ->   1) {8,0,0,0,0}
règle 1 : {1,0,0,0}, le complément 7>=1 donc ->   2) {7,1,0,0,0}
règle 1 : {2,0,0,0}, le complément 6>=2 donc ->   3) {6,2,0,0,0}
règle 1 : {3,0,0,0}, le complément 5>=3 donc ->   4) {5,3,0,0,0}
règle 1 : {4,0,0,0}, le complément 4>=4 donc ->   5) {4,4,0,0,0}
règle 1 : {5,0,0,0}, le complément 3<5 donc
règle 3 : {1,1,0,0}, le complément 6>=1 donc ->   6) {6,1,1,0,0}
règle 1 : {2,1,0,0}, le complément 5>=2 donc ->   7) {5,2,1,0,0}
règle 1 : {3,1,0,0}, le complément 4>=3 donc ->   8) {4,3,1,0,0}
règle 1 : {4,1,0,0}, le complément 3<4 donc
règle 3 : {2,2,0,0}, le complément 4>=2 donc ->   9) {4,2,2,0,0}
règle 1 : {3,2,0,0}, le complément 3>=3 donc -> 10) {3,3,2,0,0}
règle 1 : {4,2,0,0}, le complément 2<4 donc
règle 3 : {3,3,0,0}, le complément 2<3 donc
règle 3 : {1,1,1,0}, le complément 5>=1 donc -> 11) {5,1,1,1,0}
règle 1 : {2,1,1,0}, le complément 4>=2 donc -> 12) {4,2,1,1,0}
règle 1 : {3,1,1,0}, le complément 3>=3 donc -> 13) {3,3,1,1,0}
règle 1 : {4,1,1,0}, le complément 2<4 donc
règle 3 : {2,2,1,0}, le complément 3>=2 donc -> 14) {3,2,2,1,0}
règle 1 : {3,2,1,0}, le complément 2<3 donc
règle 3 : {3,3,1,0}, le complément 1<3 donc
règle 3 : {2,2,2,0}, le complément 2>=2 donc -> 15) {2,2,2,2,0}
règle 1 : {3,2,2,0}, le complément 1<3 donc
règle 3 : {3,3,2,0}, le complément 0<3 donc
règle 3 : {3,3,3,0}, le complément -1<3 donc
règle 3 : {1,1,1,1}, le complément 4>=1 donc -> 16) {4,1,1,1,1}
règle 1 : {2,1,1,1}, le complément 3>=2 donc -> 17) {3,2,1,1,1}
règle 1 : {3,1,1,1}, le complément 2<3 donc
règle 3 : {2,2,1,1}, le complément 2>=2 donc -> 18) {2,2,2,1,1}

si on essaie de poursuivre
règle 1 : {3,2,1,1}, le complément 1<3 donc
règle 3 : {3,3,1,1}, le complément 0<3 donc
règle 3 : {2,2,2,1}, le complément 1<2 donc
règle 3 : {2,2,2,2}, le complément 0<2 et on est bloqué car on ne peut plus se décaler à droite : le calcul de d(j,s) n'est donc pas nécessaire pour conditionner l'arrêt mais peut être utile pour effectuer des vérifications.

On remarque qu'on obtient encore un ordre différent.

Publié dans mathblog

Pour être informé des derniers articles, inscrivez vous :

Commenter cet article