La question du dimanche (V)

[C.Ret]

Je n'ai pas pu depuis dimanche venir poster ici.

Je donne un indice supplémentaire: ces séquences ont déjà été évoquées sur ce forum. Elles ont même déjà fait l'objet d'un MPO.

Enfin, ce n'est pas exactement le même type de séquence, mais le lien de parenté est extrêmement fort car c'est juste la distance entre les termes identique qui varie juste d'une unité.

[dprtl]

Je n'ai pas encore trouvé les références externes ou le MPO qui correspond à cette "question du dimanche". Et il n'y a pas encore d'index ou de sommaire pour celles-ci ; espérons qu'elles ne tombent pas dans l'oubli.

D'autre part, j'étais entrain de jouer avec mon nouveau Sharp PC-850VS, et je remarque que personne n'a encore publié son code ici. Peut-être que le problème L(2,7) est trop difficile pour des machines anciennes ? Pour trouver l'intégralité des 52 solutions, il faut en effet une belle puissance de calcul. Mais sans chercher l'exhaustivité, pour en trouver juste une, dans L(2,8) par exemple, ça serait peut-être abordable ?

1 6 1 3 7 5 8 3 6 4 2 5 7 2 4 8
2 3 8 2 4 3 6 7 5 4 1 8 1 6 5 7
6 2 8 4 2 7 3 6 4 5 3 8 1 7 1 5
7 3 8 6 1 3 1 5 7 4 6 8 2 5 4 2
...

[gege]

Bonjour,
Euh quelle est la question ?
Son absence m'empêche de trouver, car elle m'empêche de chercher…
A voir,
G.E.

[dprtl]

La question initiale de C.Ret était : "Mais qu'est-ce que c'est que ça ?". Ce à quoi je réponds : il s'agit de l'énumération exhaustive des 52 solutions au problème des cubes de Langford à l'ordre 7 (14 cubes de 7 valeurs différentes).

Si la question devient maintenant : comment construire ces solutions sur un pocket ou un ordinateur ancien, ça se complique un peu !

[C.Ret]

La question initiale de C.Ret était : "Mais qu'est-ce que c'est que ça ?". Ce à quoi je réponds : il s'agit de l'énumération exhaustive des 52 solutions au problème des cubes de Langford à l'ordre 7 (14 cubes de 7 valeurs différentes).

C'est bien cela, bravo !

C'est vrai que j'ai failli oublier cette QDD !

Sur un ordinateur un peu ancien, cela se fait bien, surtout pour les petites énumérations. Après pour les grands nombres… et très très grand c'est déjà à partir de vingt huit.


Quand à l'algo que j'utilise, il s'agit simplement d'une force brute. Il suffit d'organiser les choses de façon efficace en fonction de la machine ancienne utilisée.
Comme par exemple ci-dessous pour un BASIC classique typique d'un Pocket ou d'un système 8bits.

Je commence à placer k=n puis descend jusqu'à k=1.
Initialement le tableau L( ) de dimension 2.n ne contient que des zéros qui indiquent les positions libres.
En plaçant une valeur k à la position i, je sait que l'autre valeur k sera à la position j=1+i+k.
Pour placer la valeur k aux positions i et j, il faut donc que L(i) et L(j) contiennent tous les deux une valeur nulle.
Si ce n'est pas le cas, je décale i (et donc j) d'une unité sans pour autant dépasser l'extrémité située à 2n.
Il n'y a donc pas un nombre infini de possibilités.
Pour gagner du temps, les positions i des n valeurs sont mémorisées dans une pile I(k)

Si je trouve une position I(k) qui convient pour la valeur k, je continue en cherchant une valeur pour (k-1).
Si j'arrive à trouver une position pour k=1, alors j'affiche la séquence complète et continue la recherche d'une autre solution.
Inversement si aucune position n'est trouvée pour la valeur k, je remets I(k) à zéro et poursuit la recherche au niveau (k+1). Si je dépasse le niveau n, c'est que j'ai parcouru toutes les combinaisons possibles.

Code : Tout sélectionner

!------------------ Init
10 INPUT "langford order :";N
20 DIM I(N),L(2*N)
30 K=N
!------------------ SEEK LOOPS
110 DO
120 :  I(K)=0
130 :  DO
140 :  :  OK=0 : J=1+K+I(K)
150 :  :  IF L(I(K))=K THEN L(I(K))=0 : L(J)=0        !---- clean up actual k level
160 :  :  DO WHILE J<2*N                                    !---- seek one step further until j is out of bounds
170 :  :  :  I(K)=I(K)+1 : J=J+1 : OK= L(I(K))=0 AND L(J)=0
180 :  :  :  IF OK THEN L(I(K))=K : L(J)=K : EXIT    !---- set value k at positions i and j
190 :  :  LOOP
200 :  :  IF OK AND K=1 THEN F=F+1 : GOSUB1000 : OK=0 : L(I(K))=0 : L(J)=0     !----- display completed sequence L() and continue seeking
210 :  :  IF OK THEN EXIT
220 :  :  K=K+1                                                  !---- no solution found --> go back (up to level n)
230 :  LOOP UNTIL K>N
240 :  K=K-1                                                     !---- solution found  --> go next (down to level 1)
250 LOOP WHILE OK                                         !----- or stop seeking when k>n
260 PRINT "End of Seek: ";F;" found(s)."
270 END
!----------------- Display completed sequence
1000 PRINT "  [";
1010 FOR I=1 TO 2*N
1020 :  PRINT USING "###";L(I);
1030 NEXT I
1040 PRINT " ]"
1050 RETURN

Petit exemple avec n=3:

Code : Tout sélectionner

Init:
k  I()	     L()
3:  0
2:  0
1:  0  [ . . . . . . ]
Seek for 3:
3:  1  [ 3 . . . 3 . ]  OK
Seek for 2:
3:  1  [ 3 . . . 3 . ]
2:  1  [ 2 . . 2 . . ]
         ^            *nOK*
3:  1  [ 3 . . . 3 . ]
2:  2  [ . 2 . . 2 . ]
                 ^    *nOK*
3:  1  [ 3 . . . 3 . ]
2:  3  [ . . 2 . . 2 ]  OK
Seek for 1:
3:  1  [ 3 . . . 3 . ]  
2:  3  [ . . 2 . . 2 ]   
1:  1  [ 1 . 1 . . . ]
         ^   ^        *nOK*
3:  1  [ 3 . . . 3 . ]  
2:  3  [ . . 2 . . 2 ]   
1:  2  [ . 1 . 1 . . ]  OK       1st=[ 3 1 2 1 3 2 ]

3:  1  [ 3 . . . 3 . ]  
2:  3  [ . . 2 . . 2 ]   
1:  3  [ . . 1 . 1 . ]
             ^   ^    *nOK*
3:  1  [ 3 . . . 3 . ]  
2:  3  [ . . 2 . . 2 ]   
1:  4  [ . . . 1 . 1 ]
                   ^  *nOK*
1:  4  [ . . . . 1 . 1 
                     ^ too far
Seek for 2:
2:  4  [ . . . 2 . . 2
                     ^ too far
Seek for 3:
3:  2  [ . 3 . . . 3 ]  OK
Seek for 2:
2:  1  [ 2 3 . 2 . 3 ]  OK
Seek for 1:
1:  1  [ * 3 1 2 . 3 ] *nOK*
1:  2  [ 2 * . * . 3 ] *nOK*
1:  3  [ 2 3 1 2 1 3 ]  OK       2nd=[ 2 3 1 2 1 3 ] 
1:  3  [ 2 3 . * . * ] *nOK*
1:  4  [ 2 3 . 2 1 3 * too far
Seek for 2:
2:  2  [ . * . . 2 3 ] *nOK*
2:  3  [ . 3 2 . . * ] *nOK*
2:  4  [ . 3 . 2 . 3 * too far
Seek for 3:
3:  3  [ . . 3 . . . 3 * too far
End of seek.

Ce qui revient à parcourir l'arbre de recherche suivant:

Code : Tout sélectionner

                                 [......]
3:                ┌─────────────────┴───────────┐
                 [3...3.]                     [.3...3]
                   O K                           O K
2:      ┌────────┬──┴─────┐                 ┌─────┴──┬────────┐
       [2..2..][.2..2.][..2..2]            [2..2..][.2..2.][..2..2]
        nok      nok      O K               O K      nok      nok
1:  ┌────────┬────────┬────┴───┐       ┌─────┴──┬────────┬─────────┐
   [1.1...][.1.1..][..1.1.][...1.1]   [1.1...][.1.1..][..1.1.] [...1.1]
    nok      O K      nok      nok     nok      nok      O K       nok
       [ 3 1 2 1 3 2 ]                             [ 2 3 1 2 1 3 ] 

[C.Ret]

Evidemment, il y a d'autres algorithmes qui facilitent la recherche en jouant sur la symétrie, en ajoutant des compteurs et des indicateurs qui permettront des gains importants en évitant des essais infructueux.
En particulier en utilisant pour chaque niveau des compteurs donnant le nombre de couples de positions libres séparées de n, n-1, n-2, … , 1 unités. Ainsi, une position possible au niveau k peut être éliminée en anticipant l'impossibilité de placer un niveau inférieur.

[dprtl]

Mon programme est bien plus "force brute" que celui proposé par C.Ret. Comme la partie qui concerne l'énumération exhaustive de toutes les combinaisons dans l'ordre lexicographique présente un intérêt, je vous publie quand même son code source commenté ici : QUESTV03.C ainsi que le programme binaire compilé avec Pure C pour Atari ST : QUESTV03.TOS.



Ce programme m'a permis de prouver qu'il y a deux solutions à l'ordre 3 et à l'ordre 4 ; mais pas de solution à l'ordre 5 et à l'ordre 6. J'ai également énuméré l'intégralité des 300 solutions à L(2,8)... sur un cluster de 300 CPU 68k refroidis à l'eau de Lourdes.

[C.Ret]

Cela faisait longtemps que je n'avais pas eut à relire du C !
C'est intéressant la façon dont toutes les solutions sont parcourues dans l'ordre lexicographique croissant. C'est une technique bonne à connaitre qui peut rendre bien des services dans une énumération exhaustive.

C'est donc effectivement une méthode bien plus brutale que celle de mon compteur parcourant l'arbre incomplet car élagué des branches impossibles.

Je donne ci-dessous une version transcrite en BASIC pour Pocket SHARP (typiquement PC-135/1360) du programme en C de dprt.

C'est exactement le même algorithme, j'ai juste rassemblé l'initialisation des permutations et le test de la validité de la séquence à l'intérieur d'une seule boucle FOR / NEXT. Pour le test de validité, j'utilise une astuce binaire en codant dans la variable résultat OK les valeurs 'k' (variant de 1 à n) à tester. Les bits de chaque valeur 'k' sont éteint au fur et à mesure de l'avancé du test (respectivement 2, 4, 8 … 2^n). Le décalage est volontaire, le bit0 (valeur 1) sert de témoin, OK vaut donc 1 lorsque toutes les valeurs ont été testées avec succès. En cas d'échec OK est mis directement à zéro ce qui met fin au test en cours.

Code : Tout sélectionner

10 CLEAR : CLS : WAIT 0: PRINT "Langford(2,n) Sequences": INPUT "Order n=";N
20 M=2*N,T=2*2^N-1,F=0,K=1: DIM A(M): FOR I=1 TO M:A(I)= INT K,K=.5+K: NEXT I:A(0)=M
30 X=0,OK=T: FOR I=1 TO M: K=A(I),P=2^K
40 IF OK AND P LET OK=OK AND (T-P),J=1+I+K,J=J*(J<=M): IF K<>A(J) LET OK=0 
50 IF I<M IF K<A(I+1) LET X=I
60 IF A(X)<K LET Y=I
70 NEXT I: IF OK LET F=F+1: PRINT F;: USING "##": FOR i=1 TO M: PRINT A(I);: NEXT I: USING : PRINT
80 IF X FOR I=0 TO N-X/2: A=A(X+I),A(X+I)=A(Y),A(Y)=A,Y=M-I: NEXT I: GOTO 30
90 PRINT F;"found(s)":END

qdd_3.gif (28.44 Kio) Vu 6757 fois

C'est effectivement bien long, je recommande de commencer à tester avec les ordres 3 ou 4 et éventuellement d'imprimer au fur et à mesure.
Tout du moins jusqu'à avoir un peu mieux optimiser la recherche