Algorithme ???

[fanfan23]

Vous avez 9 chiffres : 1 2 3 4 5 6 7 8 9
Il y a 36 combinaisons de 2 chiffres parmi les 9 chiffres de départ :
9 8 - 9 7 - 9 6 - 9 5 - 9 4 - 9 3 - 9 2 - 9 1
8 7 - 8 6 - 8 5 - 8 4 - 8 3 - 8 2 - 8 1
7 6 - 7 5 - 7 4 - 7 3 - 7 2 - 7 1
6 5 - 6 4 - 6 3 - 6 2 - 6 1
5 4 - 5 3 - 5 2 - 5 1
4 3 - 4 2 - 4 1
3 2 - 3 1
2 1
Quel est l'algorithme qui permet de retrouver toutes les combinaisons de 3 chiffres parmi 9 recouvrant la totalité des 36 combinaisons ?

Exemple : la combinaison 1 2 5 permet de couvrir les combinaisons 1 2 - 1 5 - 2 5 donc il doit y en avoir 12, on peut les retrouver manuellement mais pour un nombre de chiffres plus grand cela peut se révéler long. Donc si vous pouviez m'aider pour l'écriture de l'algorithme.

[fatal_error]

hello,

Quel est l'algorithme qui permet de retrouver toutes les combinaisons de 3 chiffres parmi 9 recouvrant la totalité des 36 combinaisons ?

pas compris.
1-2-5, ca couvre pas les 36 couples.

Exemple : la combinaison 1 2 5 permet de couvrir les combinaisons 1 2 - 1 5 - 2 5 donc il doit y en avoir 12

pas compris non plus. pour moi 12-15-25 ca fait trois couples.

peux-tu expliciter?

[fanfan23]

hello,



pas compris.
1-2-5, ca couvre pas les 36 couples.


pas compris non plus. pour moi 12-15-25 ca fait trois couples.

peux-tu expliciter?

Si je ne me suis pas trompé les 12 combinaisons de 3 chiffres : 1 2 5 - 1 3 7 - 1 4 9 - 1 6 8 - 2 3 9 - 2 4 8 - 2 6 7 - 3 4 6 - 3 5 8 - 4 5 7 - 5 6 9 - 7 8 9 couvrent bien les 36 combinaisons de 2 chiffres citées précedemment.

[fatal_error]

donc tu cherches un ensemble de groupes de 3 chiffres, tel que avec tous ces groupes ca recouvre les 36 couples.

Je présume que tu cherches l'ensemble le plus petit possible.

C'est bien ca?

[fatal_error]

si c'est bien le cas, alors on peut représenter les choses avec une matrice d'adjacence.

Si on prend un groupe (1,2,3), on sait que on va generer les trois couples "symétriquement".
Si on écrit la matrice d'adjacence, la paire 12 c'est pareil que 21, donc on a une matrice symétrique:

avec 5 chiffres pk c'est plus court :

Code: Tout sélectionner

..1.2.3.4.5
____________
1|X|.-.|.-.|
2|X|X|.-.|.|
3|X|X|X|.-.|
4|X|X|X|X|.|
5|X|X|X|X|X|

on s'intéresse à la partie supérieure. Il suffit d'entourer des groupes de deux cases (pour faire des groupes de 3 : le premier chiffre est lu sur la ligne, les deux autres sur la colonne)

Ici, on lit :
1 2 3
1 4 5
2 3 4
3 4 5
2 5 4

Ce qui devrait suffire à générer les 2 parmi 5 paires.

[fanfan23]

donc tu cherches un ensemble de groupes de 3 chiffres, tel que avec tous ces groupes ca recouvre les 36 couples.

Je présume que tu cherches l'ensemble le plus petit possible.

C'est bien ca?

Oui
Je recherche un algorithme qui me permettrait de le faire aisément pour des nombres plus grands

[fanfan23]

si c'est bien le cas, alors on peut représenter les choses avec une matrice d'adjacence.

Si on prend un groupe (1,2,3), on sait que on va generer les trois couples "symétriquement".
Si on écrit la matrice d'adjacence, la paire 12 c'est pareil que 21, donc on a une matrice symétrique:

avec 5 chiffres pk c'est plus court :

Code: Tout sélectionner

..1.2.3.4.5
____________
1|X|.-.|.-.|
2|X|X|.-.|.|
3|X|X|X|.-.|
4|X|X|X|X|.|
5|X|X|X|X|X|

on s'intéresse à la partie supérieure. Il suffit d'entourer des groupes de deux cases (pour faire des groupes de 3 : le premier chiffre est lu sur la ligne, les deux autres sur la colonne)

Ici, on lit :
1 2 3
1 4 5
2 3 4
3 4 5
2 5 4

Ce qui devrait suffire à générer les 2 parmi 5 paires.

Je te remercie beaucoup pour ta réponse rapide mais existerait-il un algorithme permettant de générer ces combinaisons ?

[fatal_error]

ben après c'est pas la mort: au pire sans optimiser et dans les grandes lignes :


pour la matrice n,n n représentant le nombre de lettres

Code: Tout sélectionner

CellulesATraiter un ensemble d'indice de dellules

pour indiceCellule=2 a n*n
 [i,j] = getCoordonnees(indiceCellule)
 si j<=i
  //on est diagonale inferieure on sen tape
  continue
 sinon
 [x,y] = getCoordonnees(indiceCellule+1)
 si x==i
 //si la cellule d'apres est sur la meme ligne
  afficher i,indiceCellule,indiceCellule+1
  indiceCellule++; //on consomme indiceCellule+1
 sinon
 //on est passé a la ligne: indiceCellule est la fin de colonne
 CellulesATraiter.ajouter(indiceCellule)
finpour

Tant que CellulesATraiter non vide
 indice1 = CellulesATraiter.pop()
 si(CellulesATraiter.empty())
  afficher 1,2,indice1
 sinon
 indice2 = CellulesATraiter.pop()
 [i,j] = getCoordonnees(indice1)
 afficher indice1,indice2,i
finpour

[fanfan23]

ben après c'est pas la mort: au pire sans optimiser et dans les grandes lignes :


pour la matrice n,n n représentant le nombre de lettres

Code: Tout sélectionner

CellulesATraiter un ensemble d'indice de dellules

pour indiceCellule=2 a n*n
 [i,j] = getCoordonnees(indiceCellule)
 si j<=i
  //on est diagonale inferieure on sen tape
  continue
 sinon
 [x,y] = getCoordonnees(indiceCellule+1)
 si x==i
 //si la cellule d'apres est sur la meme ligne
  afficher i,indiceCellule,indiceCellule+1
  indiceCellule++; //on consomme indiceCellule+1
 sinon
 //on est passé a la ligne: indiceCellule est la fin de colonne
 CellulesATraiter.ajouter(indiceCellule)
finpour

Tant que CellulesATraiter non vide
 indice1 = CellulesATraiter.pop()
 si(CellulesATraiter.empty())
  afficher 1,2,indice1
 sinon
 indice2 = CellulesATraiter.pop()
 [i,j] = getCoordonnees(indice1)
 afficher indice1,indice2,i
finpour

Encore merci pour ta rapidité je vais essayer de tester avec algobox

[fatal_error]

jme suis planté avec ma matrice paske
1 2 3
1 4 5
2 3 4
c'est pas super.
1 2 3 recouvre 2 3 4

[fatal_error]

petit up, parce que c'est pas si facile qu'il n'y parait.

Pour 1-9 j'ai l'algo, mais c'est pas généralisable facilement.
l'idée c'est d'écrire
123 456 789
puis je note xyz, (x,y,z dans {1,2,3})
x associe le nombre en xieme position du premier groupe, y du second, et z du troisieme.
ex: xyz=213 signifie
x: deuxieme position premier groupe ->2
y: premier position deuxieme groupe -> 4
z: troisieme position troisieme groupe -> 9

Du coup on a d'emblée
111
222
333
qui sont solutions.
On veut éviter les doublons style 11z, parce que la liaison existe déjà (111)
Donc on évite le double 1, le double 2, le double 3 ce qui fait 18 possibilités.

On a en tout 3*3*3=27 possibilités. Il reste plus que 27-18-3=6 possibilités.
On a les arrangements de 123:
123
132
213
231
312
321

ce qui nous donne au final les 9 possibilités (à ajouter en plus de 123 456 789):
111
222
333
123
132
213
231
312
321
[ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]
[ 1, 4, 7 ]
[ 2, 5, 8 ]
[ 3, 6, 9 ]
[ 1, 5, 9 ]
[ 1, 6, 8 ]
[ 2, 6, 7 ]
[ 2, 4, 9 ]
[ 3, 4, 8 ]
[ 3, 5, 7 ]

Ci dessous la matrice d'adjacence. Une croix i,j signifie que le couple ij est généré. Des croix partout, tous les couples sont bien générés.

Code: Tout sélectionner

.|X|X|X|X|X|X|X|X|
.|.|X|X|X|X|X|X|X|
.|.|.|X|X|X|X|X|X|
.|.|.|.|X|X|X|X|X|
.|.|.|.|.|X|X|X|X|
.|.|.|.|.|.|X|X|X|
.|.|.|.|.|.|.|X|X|
.|.|.|.|.|.|.|.|X|
.|.|.|.|.|.|.|.|.|

Par contre de là à généraliser pour n qq ca marche pas avec cette manière d'appréhender, parce qu'on perd la permutation.

[Pluzin]

Vous avez 9 chiffres : 1 2 3 4 5 6 7 8 9
Il y a 36 combinaisons de 2 chiffres parmi les 9 chiffres de départ :
9 8 - 9 7 - 9 6 - 9 5 - 9 4 - 9 3 - 9 2 - 9 1
8 7 - 8 6 - 8 5 - 8 4 - 8 3 - 8 2 - 8 1
7 6 - 7 5 - 7 4 - 7 3 - 7 2 - 7 1
6 5 - 6 4 - 6 3 - 6 2 - 6 1
5 4 - 5 3 - 5 2 - 5 1
4 3 - 4 2 - 4 1
3 2 - 3 1
2 1
Quel est l'algorithme qui permet de retrouver toutes les combinaisons de 3 chiffres parmi 9 recouvrant la totalité des 36 combinaisons ?

Exemple : la combinaison 1 2 5 permet de couvrir les combinaisons 1 2 - 1 5 - 2 5 donc il doit y en avoir 12, on peut les retrouver manuellement mais pour un nombre de chiffres plus grand cela peut se révéler long. Donc si vous pouviez m'aider pour l'écriture de l'algorithme.

Bonjour,

Si tu piges l`Anglishe Fais un tour ici :

http://www.ccrwest.org/cover.html

C`est une encyclopedie avec un formidable outil informatique.

[fanfan23]

Bonjour,

Si tu piges l`Anglishe Fais un tour ici :

http://www.ccrwest.org/cover.html

C`est une encyclopedie avec un formidable outil informatique.

Merci je vais y faire un tour

[fanfan23]

petit up, parce que c'est pas si facile qu'il n'y parait.

Pour 1-9 j'ai l'algo, mais c'est pas généralisable facilement.
l'idée c'est d'écrire
123 456 789
puis je note xyz, (x,y,z dans {1,2,3})
x associe le nombre en xieme position du premier groupe, y du second, et z du troisieme.
ex: xyz=213 signifie
x: deuxieme position premier groupe ->2
y: premier position deuxieme groupe -> 4
z: troisieme position troisieme groupe -> 9

Du coup on a d'emblée
111
222
333
qui sont solutions.
On veut éviter les doublons style 11z, parce que la liaison existe déjà (111)
Donc on évite le double 1, le double 2, le double 3 ce qui fait 18 possibilités.

On a en tout 3*3*3=27 possibilités. Il reste plus que 27-18-3=6 possibilités.
On a les arrangements de 123:
123
132
213
231
312
321

ce qui nous donne au final les 9 possibilités (à ajouter en plus de 123 456 789):
111
222
333
123
132
213
231
312
321
[ 1, 2, 3 ]
[ 4, 5, 6 ]
[ 7, 8, 9 ]
[ 1, 4, 7 ]
[ 2, 5, 8 ]
[ 3, 6, 9 ]
[ 1, 5, 9 ]
[ 1, 6, 8 ]
[ 2, 6, 7 ]
[ 2, 4, 9 ]
[ 3, 4, 8 ]
[ 3, 5, 7 ]

Ci dessous la matrice d'adjacence. Une croix i,j signifie que le couple ij est généré. Des croix partout, tous les couples sont bien générés.

Code: Tout sélectionner

.|X|X|X|X|X|X|X|X|
.|.|X|X|X|X|X|X|X|
.|.|.|X|X|X|X|X|X|
.|.|.|.|X|X|X|X|X|
.|.|.|.|.|X|X|X|X|
.|.|.|.|.|.|X|X|X|
.|.|.|.|.|.|.|X|X|
.|.|.|.|.|.|.|.|X|
.|.|.|.|.|.|.|.|.|

Par contre de là à généraliser pour n qq ca marche pas avec cette manière d'appréhender, parce qu'on perd la permutation.

Salut, j'ai compris ton raisonnement, cependant comme tu l'as dit c'est la généralisation qui est difficile

[Pluzin]

Le probleme est d`une grande complexite.
Il existe plusieurs algorithmes qui chacun apporte une solution (voir le site donne en reference).
C`est la course a qui ferait le mieux.
Il y a meme des defis a relever si on veut voir son nom figurer au palmares des records.
Si on trouve mieux on ecrit au site sa solution.
Si elle est meilleure que d`autres, la reponse est donnee dans les 24 heures qui suivent.
Chercheurs de gloire precipitez-vous!