P = NP

Résolution du problème SAT

Avant Propos

Les problèmes du prix du millénaire sont un ensemble de sept défis mathématiques réputés insurmontables, posés par le CLAY MATHEMATIC INSTITUTE en 2000.

  1. Hypothèse de RIEMANN (constitue aussi l'un des problèmes de Hilbert)
  2. Conjecture de POINCARÉ (résolue en 2003)
  3. Problème P = NP
  4. Conjecture de HODGE
  5. Conjecture de BIRCH et SWINNERTON-DYER
  6. Équations de NAVIER-STOKES
  7. Équations de YANG-MILLS

La résolution de chacun des problèmes est dotée d'un prix d'un million de dollars américains offert par l'institut. En 2017, six des sept problèmes demeurent non résolus.

Chacun des défis consiste à :

  • soit démontrer une hypothèse ou une conjecture qui n'a été ni confirmée ni rejetée faute d'une démonstration mathématique suffisamment rigoureuse ;
  • soit définir et expliciter l'ensemble des solutions de certaines équations.

Concernant le problème P = NP, dans un article d’aout 2005, paru dans la revue Pour la Science, le professeur Jean Paul DELAHAYE écrivait (voir l'article complet) :

La question « P = NP ? » est l'un de sept problèmes que l'Institut Clay a sélectionnés en l'an 2000 : comme pour les six autres, une somme d'un million de dollars attend celle, celui ou ceux qui le résoudront. Certains affirment que c'est le plus important des sept problèmes et donc la principale énigme des mathématiques d'aujourd'hui. Il semble aussi le seul dont la résolution aurait des conséquences pratiques (il est lié à des centaines d'énoncés concrets) et sa portée philosophique est la plus grande : la question « P = NP ? » concerne la nature de la recherche de solution(s) dans un ensemble exponentiel de possibilités, ce qui est le problème même de la recherche scientifique. La question « P = NP ? » signifie à peu près : « Ce que nous pouvons trouver rapidement lorsque nous avons de la chance, peut-il être trouvé aussi vite par un calcul intelligent ? ». Très sommairement, « l'intelligence peut-elle remplacer la chance ? »

Une autre formulation est : « Tout ce que l'on peut vérifier facilement, peut-il être découvert aisément ? ». Vérifier qu'un chemin dans un graphe passe par tous les nœuds du graphe sans jamais passer deux fois par le même nœud (chemin hamiltonien) est facile, trouver le chemin n'est pas facile (aujourd'hui aucun algorithme efficace ne le permet). En revanche, si P = NP, savoir s'il existe des chemins hamiltoniens sera facile.

… Nous avons aujourd'hui de fortes raisons de craindre que la question « P = NP ? » soit d'une profonde et extrême difficulté.

La résolution pourrait surgir d'un algorithme résolvant un problème NP-complet. Les spécialistes considèrent cela improbable et pensent même que nous n'aurons pas la solution avant plusieurs dizaines d'années et par l'introduction d'idées radicalement nouvelles.

Si vous n'êtes pas familier de ce problème P = NP, voici 2 vidéos sur youtube qui sont d'un abord plus ou moins facile:

  1. Passe-temps
  2. P versus NP : exemple dans un réseau social

 

Si vous avez lu l'article du Professeur Jean Paul DELAHAYE et visionner la vidéo du Professeur GUERRAOUI, vous en avez certainement retenu que démontrer la conjecture P = NP passe par la résolution d'un problème qualifié par la communauté scientifique de NP-COMPLET.

Pour ma part, j'ai choisi d'asseoir ma démonstration sur une instance de SAT proposée par Stephen COOK lui-même sur le site du Clay Mathematic Institute. Il s'agit  de l'hébergement de 100 étudiants parmi 400 sachant qu'il existe une liste de paires d'étudiants dont la cohabitation est jugée incompatible. Vous pouvez voir l'énoncé du problème ici.

Selon COOK, produire la liste des combinaisons satisfaisant la contrainte imposée par le proviseur demanderait des siècles avec des super-ordinateurs...

En vérité, il se trompe parce que produire cette liste prend à peine 1/4 de seconde sur un vulgaire micro ordinateur !! Vous en aurez la preuve à la fin de cet exposé puisque, pour une paire de la sous liste à exlure je vous livre la liste complète des ... intervalles de combinaisons satisfaisant la contrainte.

Le problème SAT consiste à décider si une formule de la logique propositionnelle, présentée en forme normale conjonctive (CNF), est satisfiable ou non. Une formule CNF est une conjonction de clauses, et une clause est une disjonction de variables booléennes (positifs ou négatifs). Une formule CNF est satisfaisable s’il est possible d’associer une valeur logique à chacune de ses variables booléennes de telle manière que cette formule soit logiquement vraie.

Par exemple, une formule CNF  valide ressemble à ceci : {\displaystyle (A\lor \neg B\lor \neg C)\land (\neg D\lor E\lor F)}. Chaque clause contient 3 éléments.

Dans le problème que je vais traiter, chaque clause va contenir 100 éléments.  Et pour faire un pied de nez aux « super spécialistes », je vous autorise même à jouer avec mon programme en choisissant  « p » éléments parmi « N » aussi grands que vous le voulez avec la limite que  « N » ne doit pas dépasser 1200

Le problème SAT est considéré comme le "père" des problèmes combinatoires de décision. Ainsi résoudre SAT, c'est tout simplement éliminer la complexité

Les applications de l'algorithme que je vous propose sont innombrables et touchent tous les domaines de l'industrie. Citons-en quelques-uns:

  • planification
  • ordonnancement
  • factorisation
  • bio-informatique (séquencage d'adn)
  • cryptographie
  • preuve de théorèmes
  • diagnostics
  • ...
Les classes P et NP

« P» et « NP» sont ce qu'on appelle des « classes de complexité ». Les classes de complexité sont des ensembles de problèmes qui ont des propriétés communes.

L'idée sur laquelle repose ce classement, c'est de prendre des problèmes et de les ranger en fonction de leurs propriétés, en particulier de leur complexité :

  1. temporelle, c'est-à-dire le temps qu'il faut pour les résoudre, 
  2. ou spatiale, la quantité de mémoire qu'il faut pour les résoudre.

Dire qu'un problème se résout en un temps donné, c'est dire qu'on sait le résoudre dans ce temps, c'est-à-dire qu'on a un algorithme qui s'exécute dans ce temps et qui renvoie la bonne solution.

La classe de complexité P

La classe de complexité «P» regroupe tous les problèmes dits « de décision » que l'on peut résoudre en «temps polynomial».

Un algorithme en «temps polynomial» est un algorithme qui se termine en un nombre d'étapes inférieur à «nk», avec «n» représentant la taille de l'entrée, et «k» représentant un nombre quelconque, y compris de très grands nombres, tant qu'ils ne dépendent pas de «n» lui-même.

Un problème de décision, c'est un problème qui appelle une réponse binaire de type « oui » ou. « non ».

La classe de complexité NP

Il existe toute une classe de problèmes pour lesquels personne n'arrivait à construire d'algorithme s'exécutant en temps polynomial, mais sans qu'on arrive à prouver formellement que cela ne soit pas possible.

C'est ce qui a mené à considérer la classe de problèmes que l'on appelle «NP».

La classe de complexité NP  regroupe ainsi les problèmes « facilement vérifiables ».

Autrement dit, un problème décisionnel fait partie de la classe NP si, pour toutes les instances auxquelles nous pouvons répondre « oui », nous avons une « preuve », qu'on appelle aussi « un certificat,», qui nous permet de le vérifier en temps polynomial.

Les problèmes NP-COMPLET

Un problème « X » est qualifié « NP-Complet » si tout autre problème NP-Complet « Y » peut-être réduit à « X » en temps polynomial.

Les problèmes NP-Complet sont des problèmes NP qui sont difficiles à résoudre. En effet, si les instances sont trop grandes, en particulier lorsque le nombre de variables augmente, on ne sait pas résoudre le problème sans que cela prenne un temps d'exécution considérable (cas des algorithmes qui s'exécutent en temps exponentiel).

L'archétype des problèmes NP-difficiles, c'est le problème SAT, SAT est une abréviation pour « boolean SATisfiability problem », qui se traduit en français par « problème de SATisfaisabilité booléenne ».

Dans la hiérarchie des problèmes, « SAT» est ce qu'on appelle un problème mère. Dans le schéma ci-dessous, «3-SAT» en est une réduction, « clique » est à son tour une des réductions de «3-SAT», de même que «Somme de sous ensembles» ... et, ainsi de suite.

  

Cette hiérarchie permet de comprendre que si l'on démontre que le problème « sac à dos » ou le problème « Voyageur de commerce» est «NP-Complet », alors son ascendant et les ascendants de leurs ascendants sont eux aussi «NP-Complet » sans que nous ayons à le démontrer à nouveau;

Inversement, la hiérarchie montre que si l'on sait résoudre «SAT», alors il existe une solution à «Factorisation» ou à «Voyageur du commerce ».

Il ne vous aura certainement pas échappé que «Voyageur de commerce» se trouve dans les 2 branches de «3-SAT» .

En effet, «Voyageur de commerce» peut se résoudre comme une réduction de «Clique» mais aussi comme une réduction de «Somme de sous ensembles» , puisque l'on cherche une somme de distances inférieure à un «k».

Dans le problème «Somme de sous-ensemble», l'entrée est un ensemble «S» fini d'entiers strictement positifs et un entier cible «t», également entier strictement positif. La question est de savoir s'il existe un sous ensemble «S'» de «S» dont la somme est égale à «t».

Par exemple si «S» est l'ensemble {1, 2, 7, 14, 49, 98, 343, 686, 2409, 2793, 16808, 17206, 117705, 117993}, et si «t» = 138 457, alors le sous-ensemble «S'» = {1, 2, 7, 98, 343, 686, 2409, 17206, 117705] est une solution.

Le problème «Voyageur de commerce» comme le problème «Factorisation» seront repris après que nous aurons traité le problème «SAT».

Le problème SAT

Le problème SAT consiste à décider si une formule propositionnelle, exprimée comme une conjonction de disjonctions,  est satisfaisable ou non.

Une formule propositionnelle consiste, étant donné un ensemble de contraintes définies sur des variables booléennes, à décider s’il existe une assignation de valeurs aux variables satisfaisant toutes les contraintes (et éventuellement à déterminer une telle assignation).

Exemple de formule : (¬A∨B)∧(¬B∨A) qui est la traduction en langage commun de la pensée:  soit l'un soit l'autre mais jamais les deux.

La plus évidente des méthodes pour résoudre un problème SAT est de parcourir la table de vérité du problème, mais la complexité est alors exponentielle par rapport au nombre de variables.

En effet, une formule logique ne peut prendre que deux valeurs : vrai ou faux. Si vous avez n variables alors votre table de vérité va contenir (n+1) colonnes et 2n lignes. Voici un exemple avec n = 3 :

  

Présentation d'une instance de SAT

Nous avons signalé au paragraphe précédent que le problème SAT est un « problème mère ».  Résoudre SAT signifie que l'on peut résoudre le « problème du voyageur de commerce » ou celui de la « factorisation ».

Nous devons donc choisir une instance de SAT pour notre démonstration. Précisons pour ceux qui ne le savent pas ce que c'est une instance d'un problème.

Pour faire simple, le problème est le « concept général » et l'instance est « un exemple concret du problème général ».

Autrement dit, une instance d'un problème est un problème dont on fixe les paramètres. Par exemple:

Problème général: Trouver la moyenne de n valeurs.
Exemple d'instance du problème: n=3, et les valeurs sont 5, 6 et 2.

On a donc potentiellement une infinité d'instances pour un problème donné. .

Comme instance de SAT, nous allons choisir le problème de l'hébergement des étudiants tel qu'il est présenté par Stephen COOK lui même, ►ici sur le site du CLAY MATHEMATIC INSTITUTE

Il s'agit d'organiser l'hébergement de 400 étudiants sachant que :

  1. l'on ne dispose que de 100 places,
  2. il existe une liste de paires d'étudiants dont la cohabitation est jugée incompatible

Dans sa présentation Cook précise que le nombre total des combinaisons de 100 étudiants choisis parmi 400 dépasse 1080, le nombre estimé d'atomes dans l'univers observable et que par conséquent « the task of generating such a list from scratch seems to be so hard as to be completely impractical ».

La comparaison visuelle entre ces deux grandeurs est d'ailleurs éloquente.

  

Il parait donc impossible d'identifier et de nommer des éléments dont le nombre dépasse le nombre d'atomes dans l'univers observable. C'est pourtant ce que notre algorithme est capable de faire.

L'algorithme peut déterminer toutes le combinaisons pour des valeurs de «p» et de «N» respectivement bien plus supérieur à 100 et 400.
Vous aurez l'occasion de vérifier mes dires un peu plus loin

Faits remarquables
Première observation

La formule de dénombrement nous assure que chaque combinaison de «p» éléments choisis parmi «N» possède une image unique dans l'intervalle :

                 N!  
I = [1 , -------------   ] quelque soit «p» et quelque soit «N»
            p!(N - p)!  


Deuxième observation

Absolument rien ne nous interdit d'ordonner les éléments d'une combinaison (tiercé dans l'ordre par exemple). Ainsi, sous réserve de respecter l'ordre de éléments dans chaque combinaison, il est possible d'obtenir une liste ordonnée des combinaisons. La preuve. Voici par exemple ce que l'on obtient pour p = 6 et N = 49:

rang                  1 = [1,    2,    3,    4,    5,   6]

rang                  2 = [1,    2,    3,    4,    5,   7]

rang                  3 = [1,    2,    3,    4,    5,   8]

.....

rang   6 296 644 = [ 5 , 10 , 14 , 46 , 47 , 48 ]
rang   6 296 645 = [ 5 , 10 , 14 , 46 , 47 , 49 ]
rang   6 296 646 = [ 5 , 10 , 14 , 46 , 48 , 49 ] <== le maximum est atteint par les deux dernières colonnes
rang   6 296 647 = [ 5 , 10 , 14 , 47 , 48 , 49 ] <== la troisième colonne est incrémentée
rang   6 296 648 = [ 5 , 10 , 15 , 16 , 17 , 18 ] <== les 3 colonnes ont atteint leurs max la 4ème s'incrémente
rang   6 296 649 = [ 5 , 10 , 15 , 16 , 17 , 19 ] <== et rebelotte
rang   6 296 650 = [ 5 , 10 , 15 , 16 , 17 , 20 ]

............

rang 13 983 816 = [ 44 , 45 , 46 , 47 , 48 , 49 ] <== toutes les colonnes ont attient leurs max

Reconnaissez que n'importe quel informaticien un peu astucieux devrait être capable de produire une liste identique à celle-là où «N = 49» et «p = 6»

Maintenant pour p = 100 et N = 400, c'est sûr qu'au bout de quelques tours, vous exploserez les piles et les mémoires de vos processeurs ...même si vous disposez d'une dizaine de milliards de super ordinateurs !!

Pourtant, notre algorithme y arrive bien. Regardons par exemple à quoi ressemble la combinaison de rang 1080 et ses suivantes

rang 1080

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 396, 397]

rang 1080 + 1

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 396, 398]

rang 1080 + 2
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 396, 399]

rang 1080 + 3
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 396, 400]

rang 1080 + 4
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 397, 398]

rang 1080 + 5
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 397, 399]

rang 1080 + 6
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 397, 400]

rang 1080 + 7
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 398, 399]

rang 1080 + 8
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 398, 400]

rang 1080 + 9
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 393, 399, 400]

rang 1080 + 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 395, 396]

rang 1080 + 11
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 395, 397]
 
rang 1080 + 12
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 395, 398]

rang 1080 + 13
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 395, 399]

rang 1080 + 14
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 395, 400]

rang 1080 + 15
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 396, 397]

rang 1080 + 16
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 396, 398]

rang 1080 + 17
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 396, 399]

rang 1080 + 18
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 396, 400]

rang 1080 + 19
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 30, 32, 44, 47, 51, 54, 61, 72, 76, 78, 84, 88, 90, 99, 100, 103, 106, 110, 111, 115, 116, 120, 124, 131, 140, 143, 144, 151, 152, 153, 165, 170, 178, 187, 188, 191, 196, 201, 203, 204, 205, 214, 216, 219, 223, 237, 241, 243, 245, 251, 260, 264, 279, 290, 300, 307, 308, 311, 313, 323, 333, 335, 338, 339, 343, 345, 347, 350, 351, 355, 356, 382, 394, 397, 398]
Exécution du script : 4.33 secondes.

Ne vous y trompez pas. Avec un algorithme récursif classique il vous aurait fallu mémoriser 1080 étapes avant de parvenir à ce résultat. Autant dire que vous ne disposerez jamais ni du temps ni de l'espace pour parvenir à un résultat que j'obtiens en moins de 5 secondes

Troisième observation

Vous venez de constater que l'on peut associer un rang à une combinaison. Inversement à partir d'un rang, on peut retrouver la combinaison correspondante. Il existe donc une bijection entre l'ensemble «C» des combinaisons de «p» éléments choisis parmi «N» et l'ensemble «I» des nombres entiers borné par

                 N!  
I = [1 , -------------   ] quelque soit «p» et quelque soit «N»
            p!(N - p)!  

La révélation de cette bijection est le coeur de l'algorithme. Elle nous permet de raisonner sur les nombres entiers et non plus sur les combinaisons

Production d'un rang à partir d'une combinaison

Nous allons expérimenter la production d'un rang à partir d'une combinaison.

Un bouton plus bas va vous permettre d'ouvrir un formulaire qui vous permettra de choisir un « p >= 6 mais p < N»  et un « N > p et N <= 1200 »  

J'ai volontairement limité N à 1200 une valeur donc 3 fois plus grande de celle que Stephen COOK nous a affirmé qu'il est tout à fait impossible d'atteindre (400)

De même, pour ne pas alourdir mon exposé, je vous autorise à choisir 1 ou 2 ou 3 positions mais bien entendu si vous avez un  p = 150, rien ne nous interdit d'imposer la valeur de x postions pourvu que x < p

exemple: pour p = 100, N= 400 P1=1, V1=1 P2=25 V2=26, P3=26 V3=326 Voici la combinaison que vous allez obtenir

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400

Le programme complète automatiquement toutes les autres cases dans l'ordre croissant des éléments. Dans le cas présenté en exemple, si vous avez demandé de produire les 500 autres combinaisons suivantes, vous les obtiendez ... si c'est possible.

PLUS FORT !!! Vous pouvez entrer une valeur négative et donc demander les 500 autres combinaisons précédentes  - si c'est possible bien entendu -  et ... dans l'ordre inverse.

Production d'une combinaison à partir d'un rang

Nous avons déjà donné la méthode dans le paragraphe précédent. En effet, nous avons calculé le rang d'une combinaison, compris dans un intervalle

                  N!  
I = [1 , -------------   ] quel que soit p et quelque soit N (N a été limité à 1200 car le serveur n'a que 4 Go de mémoire mais c'est une valeur 3 fois plus grande que celle considérée comme infaisable par COOK)
            p!(N - p)!  

Puis à partir de ce rang, nous avons généré à votre choix les x combinaisons suivantes ou, plus fort encore, les x combinaisons précédentes.

Recherche d'intervalles de combinaisons

Dans le problème exposé par COOK, dans la liste des étudiants que l'on doit héberger, il y a une sous liste constituée de paires d'étudiants dont la cohabitation est jugée incompatible.

Pour traiter le problème, commençons donc par numéroter les étudiants de 1 à 400 de la manière suivante: e1, e2 ... ex ... e399, e400

Supposons maintenant que la liste de paires d'étudiants dont la cohabitation est jugée incompatible est la suivante: {e14, e25}, { e3, e358}, {e26, e125}.

Intéressons nous alors à la première paire  - {e14, e25} -  et regardons comment obtenir un intervalle de combinaisons où l'etudiant numéroté e25  ne se trouve jamais dans les mêmes combinaisons que l'étudiant numéroté e14 .

Pour ce faire, partons de la combinaison de rang 1, qui est la suivante:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100

Les 2 éléments de la paire se trouvent dans la même combinaison du fait de leur numérotation mais on a choisi les autres paires  pour qu'il n'en soit pas ainsi. Cela n'est pas génant pour le raisonnement parce que la programmation de ces 3 cas peuvent se paramétrer à l'initialisation du programme.

Pour l'instant, contentons-nous de relever des faits remarquables:

Première observation

L'étudiant numéroté e25 se trouve en position 25 et  ne pourra jamais être mis en position 26. Tout simpement parce que si on le décale d'une position vers la droite, il faudra mettre quelque chose en position 1. Or comme les éléments de la combinaison sont ordonnés, il faudrait mettre un étudiant numéroté e0 en position 1, ce qui n'est pas possible puisque e0 n'existe pas.

 

Deuxième observation

e25 peut prendre toutes les positions comprises entre 1 et 25. Le décalage à gauche est toujours permis

 

Troisième observation

Bémol par rapport à la 2ème observation. Pour p = 100 et N = 400, la valeur maximale en position 1 avec la valeur V1 est déterminée par un petit calcul V1 = N - p + 1 = 301. Dans ce cas, toutes les positions atteignent leuurs valeurs maximales:
301, 302, 303, 304, 305, 306, 307, 308, 309, 310, 311, 312, 313, 314, 315, 316, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400

Cette limite s'explique facilement. Si vous mettez par exemple e302 en position 1 alors le décalage à gauche fait apparaitre un e401 qui n'existe pas.

On observera au passage que si les éléments de la combinaison prennent partout leurs valeurs maximales, alors le rang correspondant ne peut être que

                400!  
            -------------   =
            100!300!  

2241854 791554337 561923210 387201698 554845411 177476295 990399942 258896013 007429693 894018935 107174320

C'est bien la valeur qu'on obtient lorsqu'on calcule le rang de la combinaison en ayant 301 en position 1

 

Quatrième observation

Notre objectif est d'obtenir une liste de combinaisons où e14 existe mais pas e25.

Pour éliminer e25 de la combinason, il suffit de mettre e26 à sa place et donc, on aura toujours le bloc e24e26 à considérer, ce qui nous donne une combinaison du type
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101

de rang 161094975 168603980 209841536 833344718 198944452 319198419 473427303 820848873 364059831.

On constate que 26 est suivi du plus petit élément (27) que l'on peut trouver à cette position. Comme on peut mettre une valeur maximale à cette position et définir un rang, la plus petite valeur à cette place définit donc   la borne basse d'un intervalle.

 

Cinquième observation

Pour avoir la borne haute de l'intervalle, il suffit que le bloc e24e26 soit suivi d'une valeur maximale, ce qui conduira au fait que toutes les autres positions prendront aussi leurs valeurs maximales.

Un petit calcul va nous donner la valeur maximale V26 applicable sur la position P26: V26 = N - p + 26 = 400 - 100 + 26 = 326 ce qui nous donne la combinaison
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400

de rang 289970955 303487164 377714766 300020492 758100014 174557155 052169146 877527972 055307694

 

Sixième observation

Nous avons un intervalle avec une borne basse et une borne haute.

Par construction, l'élément e25 ne figure jamais dans cet intervalle dont on peur compter les éléments: d = Borne haute - Borne basse + 1. ici, ce calcul nous donne: d = Borne haute - Borne basse + 1 = 128875980 134883184 167873229 466675774 559155561 855358735 578741843 056679098 691247864 éléments.

Dans un algorithme classique de parcours d'arbre, «d» aurait été le nombre de cas à tester.

Ainsi, vous le constatez , il a suffi d'à peine 1/3 de secondes pour s'épargner  128875980 134883184 167873229 466675774 559155561 855358735 578741843 056679098 691247863 tests inutiles !

Ces 6 observations suffissent pour concevoir un algorithme capable de produire la liste complète de tous les intervalles de combinaisons contenant e14 et jamais e25 .

Cliquez sur ce bouton pour visualiser la liste complète des intervalles de combinaisons.

Algorithme de résolution de l'instance de SAT

Dans le paragraphe précédent, nous avons montré comment déterminer un intervalle de combinaisons où l'élement  e25 de la paire {e14, e25}  ne se trouve jamais avec l'autre élément e14 . Il s'agit maintenant de trouver tous les intervalles où cette situation existe.

Notre situation initiale au 1er tour est la suivante:


au 1er tour


borne basse
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101
Combinaison de rang: 161094975 168603980 209841536 833344718 198944452 319198419 473427303 820848873 364059831

borne haute
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400
Combinaison de rang: 289970955 303487164 377714766 300020492 758100014 174557155 052169146 877527972 055307694

2ème tour

Le bloc {e24, e26} est décalé sur la gauche. L'élément 23 est absorbé.

borne basse
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102
Combinaison de rang: 4 538077383 201418890 217497783 672341675 415651205 352785004 619521170 450201379 325357331

borne haute
Il faut que tous les éléments à gauche et à droite du bloc {e24, e26} soit à leurs valeurs maximales, d'où la combinaison:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400
Combinaison de rang: 902223 715360115 068883276 298436570 090278386 292673704 577712268 892906347 908380302 075604916

**********

10ème tour

borne basse
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110
Combinaison de rang: 3662784 038563192 385681570 840857809 228880025 630673821 035510540 091951456 677309753 258087956

borne haute
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24, 26, 317, 318, 319, 320, 321, 322, 323, 324, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400
Combinaison de rang: 3679101 333106635 024504133 858483996 301623847 900734559 946167501 624794823 334403730 003834766

Après ce 10ème tour, on constate qu'on était en fait dans une boucle interne, propre à e25.

En effet,  e14 peut prendre toutes les positions de 14 à 1. Et sa boucle englobe celle de e25 que l'on vient de traiter. Donc, dans l'initialisation du 2ème tour de la boucle de e14, e13 est absorbé, ce qui amène e24  en position 23 et e26  en position 24, ce qui nous donne les combinaisons

borne basse
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102
Combinaison de rang: 18013340 961387043 439369886 245992692 491086588 085938765 702518967 840553172 007695309 862761031

borne haute
Comme signalé plus haut le bloc  doit être entouré sur sa gauche comme sur sa droite  des valeurs maximales
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 325, 326, 327, 328, 329, 330, 331, 332, 333, 334, 335, 336, 337, 338, 339, 340, 341, 342, 343, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 354, 355, 356, 357, 358, 359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383, 384, 385, 386, 387, 388, 389, 390, 391, 392, 393, 394, 395, 396, 397, 398, 399, 400
Combinaison de rang: 560463 697888585 533407258 003527610 548534466 748835811 535374310 439879105 621225873 739316740 591281216

►traitement de la boucle interne propre à  e25 (10 tours dans cet exemple e25 - e14 + 1)

Algorithme final

Nous venons de voir que, pour une paire {ex, ey}  avec x < y, x > 0, y <= N, trouver tous les intervalles satisfaisant une formule 

(¬e1∨e2 ∨... ex ∨ep-2 ∨ep-1 ∨ep )∧(¬e1∨e2 ∨... ex ∨ep-2 ∨ep-1 ∨ep ) ∧ ... ∧(¬e1∨e2 ∨... ex ∨ep-2 ∨ep-1 ∨ep )

nous conduit à traiter successivement epuis ex  ...

tant qu'il existe une paire {ex, ey}
    traiter e// on garde ex, on élimine ey
    traiter ex // on garde ey, on élimine ex
choisir une autre paire {ex, ey}

Le détail du traitement ey  est le suivant
  mémoriser dans PB la position  du bloc {ey-1, ey+1}
     tant que ex ne se trouve pas en Position 1
          tant que le bloc {ey-1, ey+1} ne se trouve pas en position Position(ex ) + 1
               calculer la borne basse
               calculer la borne hausse
               mémoriser l'intervalle
              décaler le bloc {ey-1, ey+1} d'une position sur la gauche
     décaler ex d'une position sur la gauche
     décrémenter PB

Le détail du traitement ex  est le même aux positions près

A l'issue des traitements on obtient la liste complète des intervalles de combinaisons  satisfaisant les contraintes imposées.