Tester toutes les permutations possibles à partir d'une liste de référence et afficher celle qui convient

Version imprimable

Voir 40 message(s) de cette discussion en une page

23/09/2018, 21h08
alex_fomine

Tester toutes les permutations possibles à partir d'une liste de référence et afficher celle qui convient

Bonsoir,
Je suis à la recherche de solution pour ce problème mathématique: Utiliser la totalité des neufs chiffres de 1 à neuf (chacun remplace une seule lettre ) pour remplacer correctement les lettres de a à i et avoir une égalité correcte dans :
a/(bc) + d/(ef) + g/(hi) = 1

où (bc) , (ef) et (hi) sont des écritures décimales et non des produits. ( ie: (bc)=10xb+c , ...)

Je voudrais écrire un programme Pascal qui peut tester toutes les permutations possibles et afficher celles qui sont des solutions, à partir de la liste 123456789.

Je ne suis qu'un amateur en programmation, j'ai essayé mais j'ai pas réussi et j'ai besoin de votre aide.

Merci d'avance,
Alex
23/09/2018, 22h38
tbc92

Le prof qui t'a proposé cet exercice est un bon prof. C'est un exercice intéressant. Un bon prof comme ça, on ne va pas saboter son travail, en te donnant la solution toute faite à son exercice. Tu as fait quoi pour chercher la solution ?
23/09/2018, 23h48
alex_fomine

Merci tbc92 !
Je suis un amateur trop vieux et trop loins du temps de l'apprentissage.. L'exercice est un défi lancé par un ami. auquel j'ai pensé longuement pour trouver rigoureusement une solution.
mais je n'ai pas réussi. voila pourquoi je voudrai renouer avec mon vieux Turbo7 et chercher une solution.

@ tbc92,

j'ai pas voulu tester sa directement en effectuant une boucle for sur tous les entiers de 111111111 à 999999999
Je veux me limiter aux permutations seulement
24/09/2018, 00h56
tbc92

Si tu testes tous les entiers de 111111111 à 999999999 , tu vas avoir les entiers comme 111111120 donc avec le chiffre 0 --> hors-périmètre. Et tu vas avoir les entiers comme 111111111 , donc répétition du chiffre 1, donc hors périmètre. Tu vas tester énormément de combinaisons hors-périmètre.

Si tu testes les nombres a de 1 à 9 , b de 1 à 9, avec b différent de a, c de 1 à 9, avec c différent de a et de b ... etc etc, tu vas diviser le temps de traitement par 3000 environ.

Un programme 'brutal', fait en appliquant le conseil ci-dessus, va aller très vite et te donner la liste des réponses en moins d'une seconde.

Tu peux même te limiter aux cas où a<d et d<g ... pour des raisons de 'symétrie'.

Bonjour, :D

Il te faut définir un tableau de 9 entiers, dont tu pourras éliminer à chaque combinaison testée les termes déjà utilisés, et à ne pas réemployer.
Code:

1 2 3 4 5 6 TYPE TabE = ARRAY[1..9] OF Byte; CONST Lini: TabE = (1, 2, 3, 4, 5, 6, 7, 8, 9); VAR Liste: TabE: // Initialisation de la variable Liste:= Lini;
Il te faut ensuite procéder à l'énumération des combinaisons, à priori très nombreuses - il y en a théoriquement 9! = 362880 - cela reste encore raisonnable, mais 9⁹ = 387420489 si l'on n'élimine pas les termes identiques, et ce sera alors très long ...

L'expression de la somme S = a/(bc) + d/(ef) + g/(hi) autorisant la permutation des 3 termes, tu peux imposer la restriction:
a < d < g qui évitera la sortie de termes identiques (comme on te l'a déjà suggéré); c'est ce qu'effectuera la triple boucle:
Code:

1 2 3 4 5 6 7 FOR a:= 1 TO 7 DO FOR d:= (a + 1) TO 8 DO FOR g:= (d + 1) TO 9 DO BEGIN ... END;
À ce stade, il ne te reste plus que 6 termes et tu peux envisager de travailler sur une liste réduite, que l'on peut établir de la façon suivante:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 PROCEDURE CalcLi(Xu, Xv, Xw, Xm: Byte; VAR L_6: TabE); VAR i, k: Byte; BEGIN k:= 0; FOR i:= 1 TO Xm DO IF (i<>Xu) AND ((i<>Xv) AND (i<>Xw)) THEN BEGIN Inc(k); L_6[k]:= i END; WHILE (k<9) DO BEGIN Inc(k); L_6[k]:= 0 END END;
Le programme deviendrait:
Code:

1 2 3 4 5 6 7 8 FOR a:= 1 TO 7 DO FOR d:= (a + 1) TO 8 DO FOR g:= (d + 1) TO 9 DO BEGIN CalcLi(a, d, g, 9, Liste); ... END;
et il ne resterait plus qu'à travailler sur 6 termes (b, c, e, f, h, i), en les combinant encore 3 par 3, et en éliminant à mi-parcours les 3 valeurs sorties d'une façon semblable
Ici cependant, l'énumération répond à des contraintes différentes.

# Autre variante: au lieu de calculer la somme des quotients S = a/(bc) + d/(ef) + g/(hi) , tu pourrais envisager celui du produit S' = S*(bc)*(ef)*(hi) = a*(ef)*(hi) + d*(bc)*(hi) + g*(bc)*(ef) ,
résultat entier pour lequel la vérification de l'égalité S' = (bc)*(ef)*(hi) ne pose pas de difficulté.

Code à vérifier - j'ai pu laisser passer des erreurs.

24/09/2018, 12h59
Flodelarab

Bonjour :coucou:

Dénombrons.
On tire 9 chiffres parmi 9, dans l'ordre, et sans répétition; c'est donc un arrangement.
Il s'agit même d'une factorielle puisque tous les éléments sont concernés.
9! = 362880

Sauf que les 3 termes de la somme sont permutables. (puisque l'addition est commutative)
Donc il y a 6 fois moins d'ordres puisque placer 3 parmi 3 dans l'ordre et sans répétition est aussi un arrangement, et même une factorielle. 3!=6.

Il y a donc 362880 / 6 = 60480 sommes uniques.

Largement faisable en force brute par un ordinateur.

En classant les numérateurs par ordre croissant, tu dois pouvoir t'en sortir sans trop réfléchir.

Citation:

et il ne resterait plus qu'à travailler sur 6 termes (b, c, e, f, h, i), en les combinant encore 3 par 3, et en éliminant à mi-parcours les 3 valeurs sorties d'une façon semblable

Ah oui. Je n'avais pas pensé à ça.
6/12=7/14 donc on risque de faire 2 fois la même sous-séquence.

:twisted: Mais si ce n'est pas les mêmes nombres, ce n'est pas la même réponse.
Donc on ne peut pas simplifier.
24/09/2018, 13h37
wiwaxia

Tester toutes les permutations possibles à partir d'une liste

Citation:

Envoyé par Flodelarab

... :twisted: Mais si ce n'est pas les mêmes nombres, ce n'est pas la même réponse.
Donc on ne peut pas simplifier.

L'énumération n'est pas la même qu'auparavant

Citation:

Ici cependant, l'énumération répond à des contraintes différentes.

:mrgreen: :mrgreen: :mrgreen:

Tester toutes les permutations possibles à partir d'une liste

Il faut reprendre la procédure de suppression de 3 termes (CalcLi), qui ne fonctionne correctement que dans le premier cas - la modification du code est minime:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
PROCEDURE CalcLi(Xu, Xv, Xw, Xm: Byte; VAR L_: TabE);
  VAR i, j, k: Byte; Lst: TabE;
  BEGIN
    i:= 0; 
    FOR j:= 1 TO Xm DO
      BEGIN
        k:= L_[j];  
        IF (k<>Xu) AND ((k<>Xv) AND (k<>Xw)) THEN 
          BEGIN
            Inc(i); Lst[i]:= k
          END
      END;
    WHILE (i<9) DO BEGIN
                     Inc(i); Lst[i]:= 0
                   END;
    L_:= Lst
  END;

Le programme se poursuit par l'imbrication de 6 boucles supplémentaires, en deux groupes de trois heureusement de plus en plus courts:

Code:

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
 
PROCEDURE EnumFHI(VAR Vf, Vh, Vi: Byte; L_: Tab);     // Calcul des 3 derniers indices (f, h, i)
  CONST Max = 3;
  VAR i, j, k, u, v, w: Byte; 
  BEGIN
    FOR i:= 1 TO Max DO
      FOR j:= 1 TO Max DO
        IF (i<>j) THEN
          FOR k:= 1 TO Max DO
            IF ((k<>i) AND (k<>j)) THEN
              BEGIN
                Vf:= L_[i]; Vh:= L_[j]; Vi:= L_[k];
                CalcS(a, b, c, d, e, f, g, h, i)
              END      
  END;
 
PROCEDURE EnumBCE(VAR Vb, Vc, Ve: Byte; L_: Tab);     // Calcul des 3 indices suivants (b, c, e) 
  CONST Max = 6; 
  VAR i, j, k, u, v, w: Byte;
  BEGIN
    FOR i:= 1 TO Max DO
      FOR j:= 1 TO Max DO
        IF (i<>j) THEN
          FOR k:= 1 TO Max DO
            IF ((k<>i) AND (k<>j)) THEN
              BEGIN
                Vb:= L_[i]; Vc:= L_[j]; Ve:= L_[k];
                CalcLi(Vb, Vc, Ve, 6, Liste);          // Suppression de 3 termes sur les 6 restants, non nuls
                EnumFHI(f, h, i, 3, Liste)
              END
  END;

Le programme présentera la structure suivante:

Code:

1
2
3
4
5
6
7
8
 
FOR a:= 1 TO 7 DO
  FOR d:= (a + 1) TO 8 DO
    FOR g:= (d + 1) TO 9 DO 
      BEGIN
        CalcLi(a, d, g, 9, Liste);     // Suppression des 3 1ers termes de la liste
        EnumBCE(b, c, e, Liste)
      END;

Je vous laisse le soin d'écrire les préambules, le calcul de la somme et la collecte des multiplets.

Ma seule appréhension est que alex_fomine, qui se déclare peu entraîné, ne se retrouve un peu largué.
C'est pourquoi je m'en suis tenu à la version la plus simple, pour la sélection des indices.

Il faudrait qu'il nous donne son avis :D

salut

defini a l'aide de permutation

Code:

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
 
type
  TItem = Integer;                // declare ordinal type for array item
  TArray = array[0..8] of TItem;
 
const
   Source: TArray = (1,2,3,4,5,6,7,8,9);
 
 
 
procedure Permutation(K: Integer; var A: TArray);
var
  I, J: Integer;
  Tmp: TItem;
 
begin
  for I:= Low(A) + 1 to High(A) + 1 do
  begin
    J      := K mod I;
    Tmp := A[J];
    A[J]  := A[I - 1];
    A[I - 1]:= Tmp;
    K:= K div I;
  end;
end;
 
Function TestValidite(St : String) : Boolean;
var
  iCpt   : Integer;
  I1,I2,I3: Integer;
  C1,C2,C3 : Currency;
begin
  C1  := 0;
  C2 := 0;
  C3 := 0;
  for iCpt:= 0  to  2  do
  begin
    I1 := Strtoint(ST[iCpt*3+1]);
    I2 := Strtoint(ST[iCpt*3+2]);
    I3 := Strtoint(ST[iCpt*3+3]);
     //  a/(bc) + d/(ef) + g/(hi) = 1
    Case iCpt of
      0 : C1  := I1/(I2*I3);
      1 : C2 := I1/ (I2*I3);
      2 : C3 := I1/ (I2*I3);
    end;
  end;
  Result :=  C1 +C2+C3 = 1;
end;
 
Procedure Process;
var
  A: TArray;
  I, K, Count: Integer;
  S, S1, S2: ShortString;
begin
  //////////////////////////////////
  // on détermine ne nombre d’éléments a trouver
  //////////////////////////////////
  Count:= 1;
  I:= Length(A);
  while I > 1 do
  begin
    Count:= Count * I;
    Dec(I);
  end;
  //////////////////////////////////
  S:= '';
  for K:= 0 to Count - 1 do
  begin
    A:= Source;
    Permutation(K, A);
    S1:= '';
    for I:= Low(A) to High(A) do
    begin
      Str(A[I]:1, S2);
      S1:= S1 + S2;
    end;
    if TestValidite(S1) Then 
      S:= S + '  ' + S1;
    if Length(S) > 120 then
    begin
      Ecrit(S);
      S:= '';
    end;
  end;
 
  if Length(S) > 0 then
    Ecrit(S);
end;

24/09/2018, 16h23
Flodelarab
C'est quand même extra-ordinaire qu'une seule combinaison corresponde à l'unité.
Alors que 3 correspondent à 0.95:
Code:

1 2 3 6/14 + 7/35 + 9/28 = 0.95 6/24 + 7/35 + 9/18 = 0.95 7/42 + 8/15 + 9/36 = 0.95
Ou 6 pour 0.0611111

Ou plus ... pour ...
24/09/2018, 17h08
alex_fomine

Vous êtes vraiment formidables, anapurna, wiwaxia, flodelarab et tbc92 et je vous remercie infiniment pour votre aide et votre serviabilité.

C'est vrai que j'ai du mal à me rappeler de l'algorithmique et de la syntaxe Pascal après tant d'années d'éloignement et 'd'abstinence informatique'..
Mais ce que vous avez proposé est tout à fait clair et cela réduit effectivement le temps d'exécution et élimine les répétitions et les cas superflus..

Il ne me reste plus que écrire et compiler.

Même si je serai très reconnaissant si vous pouvez me donner le listing en entier, optimisé et prêt à l’exécution. Car je vous rappelle notre but était de s'assurer quand à l'unicité d'une solution déjà trouvée (par tâtonnement).

Cordialement,
Alex
24/09/2018, 18h01
anapurna

salut

bon bin je trouve 48 réponses possible

598742136 598724136 598742163 598724163 598163724 598163742 598136724 598136742 589742163 589724163 589742136
589724136 589163742 589163724 589136742 589136724 742598136 724598136 742598163 724598163 163598742 163598724
136598742 136598724 742589163 724589163 742589136 724589136 163589724 163589742 136589724 136589742 742163598
724163598 742136598 724136598 163724598 163742598 136724598 136742598 742163589 724163589 742136589 724136589
163724589 163742589 136724589 136742589

a quelques erreurs prés le programme fournis fonctionne
24/09/2018, 18h27
alex_fomine

@anapurna

Mais pardonnez-moi, je pensais que nous étions d'accord que (bc) , (ef) et (hi) sont les écritures décimales et non pas des produits !
(bc)=10*b+c et non pas b*c

le code est à rectifier
Merci
24/09/2018, 18h43
anapurna

salut

autant pour moi j'avais raté cette épisode
le programme est assez claire pour faire la modification sans trop de difficulté

le résultat est donc 6 912534768 912768534 768912534 534912768 768534912 534768912
24/09/2018, 19h12
alex_fomine

@anapurna

Merci beaucoup pour votre aide. Bien sur que vous avez fait tout et que la rectification est simple avec votre code très clair.

Une bonne soirée à vous et à tous ceux qui m'ont aidé.

Alex

bj,

je confirme anapurna
(12lignes, nodejs)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 var t = (a,v)=>{return v[a]/(10*v[a+1]+v[a+2])} function perm(v,L){ if(v.length==9){ return t(0,v)+t(3,v)+t(6,v)==1 && console.log(v) } for(var i = 0; i<L.length; ++i){ v.push(L.splice(i,1)[0]); perm(v, L); L.splice(i,0,v.pop()); } } perm([], [1,2,3,4,5,6,7,8,9])
Code:

1 2 3 4 5 6 7 [ 5, 3, 4, 7, 6, 8, 9, 1, 2 ] [ 5, 3, 4, 9, 1, 2, 7, 6, 8 ] [ 7, 6, 8, 5, 3, 4, 9, 1, 2 ] [ 7, 6, 8, 9, 1, 2, 5, 3, 4 ] [ 9, 1, 2, 5, 3, 4, 7, 6, 8 ] [ 9, 1, 2, 7, 6, 8, 5, 3, 4 ]
a noter que c'est 6 parce que permutation ~~circulaire~~ des triplets <912>, <768>, <534>

je suis quasi sûr qu'on peut faire élégamment sans avoir recourt au brute force...(ce qui est passablement triste)

par ex, a/(10b+c)...
en mettant au même dénorminateur, puis modulo 10, on peut déduire, gcf=0[i], cqui implique i!=5, i!=7 (et par perm pareil pour c et f)

25/09/2018, 10h45
anapurna

salut

tu essai de nous dire que les nombre de 1 a 9 mises en triplet ne peut produire que factoriel de 3 solutions (6)
est par conséquent lorsque l'on trouve le premier terme nous pouvons l’Éliminé de la recherche du second et ainsi de suite jusqu’à l'obtention des trois premier termes d'un triplet
que nous pourrons à loisir redistribuer

effectivement cela pourrait grandement augmenter la vitesse le truc est donc de trouver le premier triplet
25/09/2018, 11h06
wiwaxia

Tester toutes les permutations possibles à partir d'une liste
Bonjour, :D

Ce point a été clairement exposé (#6):

Citation:

Envoyé par Flodelarab

... Dénombrons.
On tire 9 chiffres parmi 9, dans l'ordre, et sans répétition; c'est donc un arrangement.
Il s'agit même d'une factorielle puisque tous les éléments sont concernés.
9! = 362880

Sauf que les 3 termes de la somme sont permutables. (puisque l'addition est commutative)
Donc il y a 6 fois moins d'ordres puisque placer 3 parmi 3 dans l'ordre et sans répétition est aussi un arrangement, et même une factorielle. 3!=6.

Il y a donc 362880 / 6 = 60480 sommes uniques ...

(9!/3!) configurations à vérifier pour l'équation 1 = a/(bc) + d/(ef) + g/(hi) vérifiant
a < d < g .

Une triple boucle du type:
Code:

1 2 3 4 5 6 7 FOR a:= 1 TO 9 DO FOR b:= 1 TO 9 DO IF (a<>b) THEN FOR c:= 1 TO 9 DO IF ((c<>a) AND (c<>b)) THEN ...
obligerait à vérifier (9!) configurations, soit six fois plus (ce n'est évidemment pas le bout du monde ...) et livrerait les 6 permutations numériques de la somme des 3 termes; c'est d'ailleurs bien ce qui s'est passé.
25/09/2018, 11h28
anapurna

salut

le premier terme du triplet est assez simple a trouver
nous prenons la valeur maximal 9 et la divisons par la valeur minimal 1*10+2
se qui devrais considérablement diminuer le nombre de combinaison possible
26/09/2018, 23h56
wiwaxia

1 pièce(s) jointe(s)

Tester toutes les permutations possibles à partir d'une liste

Il est amusant, ce sujet.

On peut, une fois mis au point l'algorithme d'énumération, récupérer les valeurs extrêmes de la somme, et toutes les solutions situées dans un domaine donné, ici (1 - e) et (1 + e) si l'on s'intéresse aux résultats au voisinage de l"unité.

Pièce jointe 415218

Les 60480 résultats se répartissent entre 0.06829 et 1.16448, ce qui conduit à une densité linéique moyenne environ égale à 55.2E3 ; on trouve ici 41 valeurs dans le créneau choisi (e = 0.004), d'où une densité locale plus faible ~ 5.13E3 .

Il serait intéressant de tracer l'histogramme: on obtiendrait probablement une courbe en cloche, présentant un maximum dans sa partie centrale (s ~ 0.6).

Voir 40 message(s) de cette discussion en une page