Camille reçoit six fiches dans l’ordre 2, 6, 3, 4, 1, 5. Nora souhaite en conserver le plus possible avec des numéros strictement croissants, sans changer leur ordre d’arrivée. Les fiches écartées restent dans le dossier. Elle ne demande pas de trier toutes les valeurs ni de les corriger. Une sélection peut sauter des positions ; elle ne peut revenir chercher après coup une fiche qui se trouvait avant celle déjà retenue.
Cette file et ses numéros sont créés pour l’exercice. Ils ne mesurent ni prix, ni priorité réelle, ni qualité d’un objet. Les méthodes de sous-suite croissante et de classement en piles sont classiques. Les gestes décrits se font sur la feuille stipulée, sans dispositif ou service matériel essayé. Nous distinguons la sélection conservée, le résumé utilisé pour la construire et les fiches retirées d’une remise particulière.
Notice P1 du Met : catégorie Drawings.
Notice P2 du Met : catégorie Drawings.
Notice P3 du Met : catégorie Drawings.
Les notices sont citées pour leurs catégories textuelles ; aucune image, composition ou méthode d’artiste n’est utilisée pour réordonner les fiches.
Une petite fin peut laisser plus de possibilités à la suite
Camille commence par 2 puis garde 6, puisque ces deux premières valeurs montent. Quand 3 arrive, elle propose de le laisser de côté : ajouter 3 à la sélection 2,6 la ferait descendre. Nora ne demande pourtant pas d’abandonner toute sélection de deux. Elle garde 2,3 comme une autre possibilité. Cette sélection finit plus bas que 2,6 et pourrait encore recevoir 4 ou 5, que 6 n’admet pas comme prolongements croissants. Nora écarte donc 6 du résumé des fins de longueur deux, sans déclarer que la fiche 6 aurait disparu de la file reçue.
Pour une même longueur, la plus petite fin est suffisante afin de savoir si une nouvelle valeur peut prolonger une sélection. Si une valeur future dépasse une fin plus grande, elle dépasse aussi la plus petite ; certaines dépassent seulement cette dernière. Camille ne fusionne pas les deux chemins pour fabriquer 2,6,3. Elle conserve un témoin réel auprès de la petite fin et le compte deux pour sa longueur. La comparaison a retiré une fin moins favorable du résumé de possibilités, pas ajouté à la sélection tous les éléments des chemins examinés.
La fiche 4 prolonge ensuite 2,3, donnant trois valeurs. À ce moment, le résumé des petites fins est 2 pour une valeur, 3 pour deux, 4 pour trois. Quand 1 arrive, il améliore la fin possible pour une valeur seule, qui devient 1. Il ne remplace pas le premier 2 à l’intérieur du témoin 2,3,4 : sa fiche vient après 3 et 4. Nora conserve 1 comme nouvelle possibilité de longueur un, ainsi que le témoin ancien de longueur trois. Elle refuse le relevé 1,3,4 comme sous-suite effectivement retrouvée dans cet ordre.
L’arrivée de 5 prolonge le témoin 2,3,4 et donne 2,3,4,5. Le résumé final des fins est pourtant 1,3,4,5. Cette ligne décrit la plus petite fin connue pour chacune des longueurs un à quatre ; elle n’est pas une seule sélection composée de ses quatre colonnes. Nora retire son impression comme proposition de service. Elle remet 2,3,4,5, aux positions une, trois, quatre et six de la file, et conserve la ligne 1,3,4,5 dans le calcul seulement. Le résumé et le témoin ont chacun un emploi renseigné, sans que l’un se substitue silencieusement à l’autre.
Choisir la colonne qui change sans perdre les autres longueurs
Camille demande comment placer une fiche nouvelle dans le résumé. Nora cherche la première fin supérieure ou égale à sa valeur. La valeur remplace cette fin dans sa colonne, ou ouvre une nouvelle colonne si elle dépasse toutes les fins présentes. Sur 2 puis 6, les deux colonnes sont 2 et 6. La fiche 3 remplace la deuxième, donnant 2 et 3, et non 3 et 6. Les longueurs qui restent possibles doivent garder leurs fins minimales ; le choix de colonne ne suit donc pas simplement la dernière case écrite dans le relevé.
Les fins successives sont strictement croissantes. Une sélection de longueur trois finissant à 4 possède une sélection de longueur deux obtenue en retirant son dernier élément, avec une fin plus petite que 4. La plus petite fin pour deux éléments est au plus celle de ce préfixe. Nora peut donc chercher la première fin qui n’est pas inférieure à la nouvelle valeur dans une ligne déjà ordonnée. Elle ne prend pas comme justification le seul fait que les exemples 2,3,4 avaient l’air rangés : la propriété vient des sélections dont chaque colonne conserve un témoin.
Dans le relevé 2,3,4, recevoir 1 change la première colonne seulement. Aucun ancien chemin de longueur deux ou trois ne peut être prolongé par 1, puisqu’il lui faudrait une fin plus petite que 1 parmi les fiches antérieures. Recevoir 5 ensuite ajoute une quatrième colonne, car 5 dépasse la fin 4 de longueur trois. Nora joint cette décision à la position six, qui contient effectivement 5. Le changement de 2 en 1 dans la première colonne n’a pas obligé les autres témoins à recommencer après 1 ; leurs origines conservées restent antérieures au geste qui les a résumés.
Une cinquième colonne n’a jamais été ouverte. Nora peut expliquer pourquoi le calcul n’aurait pas laissé une sélection plus longue cachée. Pour tout nouveau témoin finissant à la valeur reçue, retirer son dernier élément donne un témoin antérieur dont la fin est plus petite. Le résumé conservait une fin au moins aussi petite pour cette longueur. Si un prolongement supplémentaire avait été possible, la recherche de colonne l’aurait donc reconnu. La remise de quatre valeurs est maximale pour cette file, sans que Camille ait eu à vérifier seulement une liste de propositions choisies à l’avance.
Conserver des origines qui ne se remplacent pas avec les fins
Nora prépare un relevé distinct des prédécesseurs. La fiche 3 conserve la fiche 2 comme origine de son chemin de longueur deux. La fiche 4 conserve 3, et la fiche 5 conserve 4. Pour reconstruire la sélection finale, Camille part de la position de 5 et suit ces indications : 5, 4, 3, 2 en sens inverse. Elle les retourne et remet 2,3,4,5 avec leurs positions. La fiche 1 a modifié une case du résumé, mais aucun de ces liens anciens n’a été effacé pour pointer vers elle.
Camille avait voulu faire pointer 3 vers le contenu actuel de la première colonne, devenu 1. Cette réparation donnerait un chemin de valeurs croissantes, mais sa position irait de la cinquième fiche à la troisième. Nora refuse ce lien. Elle conserve l’origine telle qu’elle a été enregistrée lors de l’arrivée de 3, quand 2 était une fiche disponible devant elle. Les colonnes contiennent des repères qui peuvent changer ; les liens du témoin contiennent des positions anciennes précises. La reconstruction doit suivre ces dernières, pas relire la colonne mise à jour longtemps après la décision.
Le premier 6 avait lui aussi enregistré 2 comme prédécesseur. Son chemin 2,6 reste un témoin de longueur deux, même quand 3 fournit une fin préférable. Nora le garde hors du résumé actif, avec sa position propre, sans le convertir en un chemin 1,6. L’histoire permet alors de contrôler une demande qui obligerait à conserver 6. Camille ne prétend pas que la meilleure fin pour une longueur donnée serait la seule suite qui ait jamais existé. Un résumé minimal suffit pour les prolongements futurs, mais il ne remplace pas l’inventaire des fiches dans une demande ultérieure.
Répartir toute la file en groupes qui ne montent pas
Une autre demande conserve maintenant toutes les fiches, dans leur ordre relatif au sein de chaque groupe, et veut le moins de groupes possible dont les numéros soient non croissants. La même procédure fournit quatre groupes : 2 puis 1 ; 6 puis 3 ; 4 seul ; 5 seul. Camille remet ces quatre listes en conservant les positions d’origine. La fiche 3 a rejoint le groupe qui finissait à 6 et la fiche 1 celui qui finissait à 2. Aucune fiche n’a été supprimée pour rendre ce partage plus petit.
Pourquoi quatre groupes sont-ils nécessaires ? La sélection croissante 2,3,4,5 comporte quatre fiches. Deux d’entre elles ne peuvent appartenir au même groupe non croissant, puisqu’elles apparaissent dans cet ordre avec une valeur plus grande à la seconde. Chaque groupe peut donc recevoir au plus une des quatre. Nora refuse une remise de trois groupes pour toutes les fiches, avec ce témoin qui ne dépend d’aucune répartition essayée. Les quatre groupes listés atteignent la borne. La sélection croissante certifie le minimum du partage sans devenir elle-même l’une de ses listes non croissantes.
Camille propose de placer 4 après 3 dans le deuxième groupe pour économiser le troisième. Ce groupe deviendrait 6,3,4, avec une montée au dernier passage. Nora le retire du partage et remet 4 seul. Elle ne transforme pas « non croissant » en « finit plus bas que son premier numéro » pour accepter ce groupe : 4 reste plus bas que 6, mais le passage de 3 à 4 viole la condition locale. La borne donnée par les quatre fiches croissantes continue également d’interdire trois groupes, même si un déplacement semblait gagner une liste dans ce projet précis.
La procédure a réellement conservé des groupes non croissants parce qu’elle place chaque valeur sur le premier groupe dont la dernière valeur est supérieure ou égale à elle. Une fiche n’est donc jamais ajoutée après une valeur plus petite à l’intérieur du même groupe. Quand une nouvelle colonne s’ouvre, sa valeur dépasse toutes les fins précédentes ; le lien vers le témoin de la colonne précédente construit une sélection croissante de cette nouvelle longueur. Le partage en groupes donne ainsi une borne supérieure et la reconstruction croissante une borne inférieure identique. Nora remet les deux certificats, qui se contrôlent mutuellement dans la file reçue.
Deux fiches de même numéro changent une interdiction stricte
Nous remplaçons la file par quatre occurrences nommées a, b, c et d, portant respectivement 2,2,1,2. Elles restent distinctes même lorsque leurs numéros sont égaux. Nora garde d’abord la montée strictement croissante. Les trois occurrences de 2 ne peuvent toutes figurer dans une telle sélection, puisqu’aucun 2 ne dépasse un autre 2. Camille choisit c puis d, valeurs 1 puis 2, aux deux dernières positions. Nora refuse la sélection a,b,d sous ce critère, mais ne supprime aucune de ces occurrences du relevé complet.
Avec la recherche de la première fin supérieure ou égale, l’arrivée de b remplace a dans la première colonne sans en ouvrir une deuxième. c y remplace ensuite le numéro 2 par 1 ; d ouvre alors une deuxième colonne. Deux est bien le maximum strict. Pour partager toute cette file en groupes non croissants, Camille reçoit a,b,c dans le premier, de valeurs 2,2,1, et d dans le second. L’égalité 2,2 y est autorisée. Le témoin c,d de longueur deux interdit un seul groupe ; les deux groupes remis atteignent donc encore la borne attendue sous les deux conventions correspondantes.
Nora exige maintenant que chaque groupe descende strictement. Elle refuse a,b,c comme liste unique, car a et b ont le même numéro. Camille doit chercher la première fin strictement supérieure à la nouvelle valeur pour la rejoindre, au lieu d’utiliser supérieure ou égale. a ouvre une colonne, b en ouvre une deuxième, c rejoint celle de a, puis d en ouvre une troisième. Les groupes sont a,c ; b seul ; d seul. Les trois occurrences a,b,d de même valeur ne peuvent partager un groupe strictement décroissant ; elles certifient donc que trois est un minimum, et pas seulement le résultat d’un autre réglage de la recherche.
Dans cette convention, le témoin dual n’est plus une sélection strictement croissante, mais non décroissante : a,b,d vaut 2,2,2 et comporte trois occurrences dans leur ordre. Nora conserve ce changement de critère auprès du nombre trois. Elle ne lui attribue pas la borne deux obtenue pour la montée stricte, et ne réétiquette pas b pour lui donner une valeur différente. Le choix de traiter l’égalité comme autorisée dans un groupe ou comme interdite a changé à la fois le placement effectué et la propriété que son certificat doit remplir.
Une suppression autorisée ne coûte pas comme un rangement
Revenons à la première file 2,6,3,4,1,5. Nora autorise maintenant uniquement de retirer des fiches pour laisser une file entière strictement croissante. Elle n’autorise aucun déplacement ni remplacement de numéro. Camille retire les positions deux et cinq, portant 6 et 1. Elle remet 2,3,4,5 dans leur ordre initial. Deux retraits suffisent. Un seul ne suffirait pas, car il laisserait cinq valeurs alors que le maximum croissant de cette file est quatre. Nora conserve cette justification avec les deux occurrences réellement retirées, plutôt qu’avec une simple différence de nombres.
Camille propose de garder les six et d’imprimer 1,2,3,4,5,6. Nora refuse ce résultat sous le menu des actes reçus. Il a changé l’ordre des fiches, opération qui n’était pas disponible. Il n’est pas une sélection de six positions dans la file initiale. Elle maintient les deux retraits et la remise de quatre, sans raconter une disparition provisoire suivie d’une réinsertion des fiches ailleurs. Les groupes non croissants de la branche précédente conservaient les six ; cette nouvelle préparation en retire effectivement deux. Les deux livrables répondent à des demandes distinctes.
Une promesse oblige maintenant à garder la fiche 6 de la deuxième position. Les valeurs après elle sont 3,4,1,5, toutes plus petites ; aucune ne peut la suivre dans une montée stricte. Avant elle, seule la fiche 2 peut être gardée. Nora remet donc 2,6, retire les quatre autres et inscrit quatre retraits comme minimum pour cette demande. La fiche promise n’a pas simplement été ajoutée au témoin 2,3,4,5 : sa place et sa valeur rendent ce témoin incompatible. La preuve du maximum quatre sans promesse n’annonçait aucune économie de deux retraits quand une autre occurrence devait obligatoirement rester.
La destinataire demande pourtant de garder ensemble 6 et la fiche 3 immédiatement suivante. Nora refuse la demande de montée stricte, quel que soit le nombre de retraits parmi les autres fiches. Les deux positions conservées imposeraient 6 puis 3. Ajouter des suppressions autour d’elles ne change ni leur ordre relatif ni cette descente. Camille ne leur donne pas un coût de six en espérant que le plus grand prix finirait par rendre la commande réalisable. Elle joint l’incompatibilité précise et demande quelle obligation doit être retirée avant de choisir une autre remise.
Nora conserve 6 et renonce à garder 3. Camille active 2,6 et marque 3 retirée avec 4,1,5. La suppression est une décision effectivement remplie dans cette branche, sans correction du numéro 3. L’ancienne sélection de quatre reste possible si la promesse 6 est abandonnée, mais elle n’est pas remise sous le même contrat. Le dossier garde les deux choix de retrait avec leurs occurrences, et les groupes non croissants avec toutes les fiches. Un résumé des fins n’a ni trié la file ni résolu ces demandes supplémentaires à la place de leur examen.
Les catégories des notices citées ne fournissent ni les numéros ni les règles de sélection ; elles demeurent les seules relations documentaires retenues.
Une hausse plafonnée oblige à garder d’autres fins possibles
Une branche distincte donne les cinq fiches 1,5,6,7,8 dans cet ordre. Nora exige encore une sélection strictement croissante sans déplacement, mais ajoute une permission plus étroite : chaque hausse entre deux fiches retenues doit être au plus deux. Les fiches sautées ne servent pas de relais invisible à cette comparaison. La distance autorisée porte sur les deux valeurs effectivement consécutives de la remise. Nora demande le plus de fiches possible sous cette nouvelle règle ; elle n’a pas donné des poids aux identités ni limité la taille de groupes dans une partition.
Camille conserve d’abord 1 comme meilleure fin pour une sélection d’une fiche. Quand 5 arrive, il ne peut suivre 1 : leur hausse vaut quatre. Camille voudrait alors le laisser hors de toute mémoire, parce que 1 reste la plus petite fin de longueur un. Nora refuse ce retrait. Une future fiche 6 pourrait suivre 5 avec une hausse de un, mais ne pourrait suivre 1 avec une hausse de cinq. Une future fiche 2 ferait l’inverse : elle pourrait suivre 1, pas 5. Ni l’une ni l’autre fin ne conserve désormais toutes les possibilités de l’autre. Nora garde donc les deux occurrences comme témoins de longueur un, avant l’arrivée de 6. La domination des plus petites fins sous la seule croissance ne se transporte pas vers cette permission ; la correction change effectivement les états conservés et non le nom de la valeur considérée comme préférable.
Nora remplit les meilleurs chemins finissant à chaque fiche avec la nouvelle fenêtre. Une valeur x peut recevoir seulement une fiche précédente y telle que x moins deux soit inférieur ou égal à y, et y strictement inférieur à x. Pour 6, la fenêtre comprend 4 et 5 : la fiche 5 fournit le chemin 5,6, de longueur deux, tandis que 1 reste exclue. Pour 7, les précédentes admissibles sont 5 et 6 ; le chemin finissant à 6 est plus long et produit 5,6,7. Pour 8, les précédentes admissibles sont 6 et 7 ; celle de 7 donne 5,6,7,8. Les meilleures longueurs par position sont donc un, un, deux, trois, quatre. Camille remet les quatre dernières fiches avec leurs hausses un, un et un, et garde 1 hors de cette sélection. La mémoire qui aurait jeté 5 parce que 1 était plus petit aurait perdu cette construction avant son premier prolongement.
Les cinq fiches ensemble ne conviennent pas, à cause du passage de 1 à 5 ; aucune sélection de cinq différente ne peut exister dans une file de cinq positions. La remise de quatre est donc maximale. Nora retire également le projet 1,6,7,8, qui semblait garder la même longueur avec une petite première valeur : son premier passage vaut cinq et reste interdit. Elle conserve 5,6,7,8 et la règle des fenêtres, avec les positions qui l’ont remplie. L’ancien calcul de fins minimales demeure sous la commande de croissance sans plafond, où il était valable ; le nouveau ne le corrige pas rétroactivement. Il a retiré une garantie de domination qui ne valait plus après restriction des prolongements et conservé précisément la fiche nécessaire au chemin remis.