combinaison d'un nombre a 12 chiffres + contraintes

combinaison d'un nombre a 12 chiffres + contraintes - C++ - Programmation

Marsh Posté le 31-03-2009 à 21:23:43    

Bonsoir a tous
 
J ai un soucis concernant un casse tete pour lequel je ne parviens pas a trouver de solution.
 
Je cherche le nombre de combinaison possible de 12 chiffres utilisant les chiffres de 0 a 9. J ai donc 10^12 possibilitees.
Pour programmer cela j utilise 12 boucles for imbriquees:  
 

Code :
  1. for(a=0;a<10;a++)
  2. ...


Puis je presente les chiffres les un a cote des autres pour faire le nombre. Je ne cherche pas a stocker etant donner que cela me ferai creer un fichier super lourd.
C est un programme facile a realiser, peut etre pas super optimal mais on fait avec (si vous avez des meilleurs idees je suis preneur).
 
 
La ou j ai un probleme c est qu il me faut maintenant enlever les combinaisons ou le meme chiffres apparait plus de 3 fois dans le nombre, ou meme beaucoup mieux, ne pas calculer les combinaisons ou plus de 3 chiffres se repetent (exemple: 111 123 456 787).
 
Avec un probleme ou je n ai que 3 chiffres formant le nombre tout va bien mais avec 12 chiffres les combinaisons sont tres tres nombreuses et je ne m en sort pas, je pense que cela vient d un manque de pratique et de logique.
 
Comment ferriez vous pour realiser la condition: si ce chiffre est deja apparu 3 fois alors il ne peut plus apparaitre a nouveau, sans utiliser:
 

Code :
  1. if(!((a==b && b==c) || ....)


 
Merci de votre aide par avance
 
Bonne soirée
 
ps: désolée pour le manque d'accent: clavier qwerty.

Message cité 1 fois
Message édité par jeje87a le 31-03-2009 à 21:24:01
Reply

Marsh Posté le 31-03-2009 à 21:23:43   

Reply

Marsh Posté le 31-03-2009 à 22:54:59    

Salut,
 
Alors déjà j'utiliserai un tableau pour stocker les 12 chiffres (ça évide les divisions pour retrouver les chiffres).
 
Ensuite un deuxième tableau de 10 entiers initialisés à 0, que j'incrémenterais suivant les chiffres de mon nombre (un 2 dans mon nombre -> j'incrémente la case d'indice 2).
Une fois le 2e tableau remplis il suffit de tester si plus de 3 zéros, uns, ... éventuellement incrémenter un compteur a chaque fois qu'il y en a au moins deux pour tester le nombre de doublons.
 
(Pour l'histoire des nombres qui se suivent c'est plus simple un entier pour connaitre le dernier nombre testé et un autre pour le nombre de fois qu'il a été lu)
 
Finalement sauter tous les nombres qui satisfont cette condition en recherchant parmi les chiffres fautifs trouvés précédemment le 1er dans ton nombre en commençant par les unités, une fois ce chiffre trouvé l'incrémenter (ne pas oublier la retenue si le nombre est dans un tableau).
Sinon si le nombre peut être afficher, incrémenter normalement pour passer au suivant.
 
Voilà une idée, bon courage pour en faire un programme.

Reply

Marsh Posté le 01-04-2009 à 13:25:57    

Merci de ton aide
 
Malheureusement je n arrive toujours pas a coder correctement.
Quelqu un aurait une piste?
 
Merci par avance

Message cité 1 fois
Reply

Marsh Posté le 01-04-2009 à 16:01:42    

jeje87a a écrit :

Malheureusement je n arrive toujours pas a coder correctement.
Quelqu un aurait une piste?


 
Acheter un bouquin, prendre des cours.
 
Sérieusement, c'est quoi la question ?

Reply

Marsh Posté le 01-04-2009 à 16:16:18    

Merci de ta réponse.
 
Ma question me semble simple, est ce que quelau'un sur ce forum peut me mettre sur la voie pour pouvoir coder le probleme.
Je te l'ai dit, ta solution semble intéressante mais elle ne fonctionne pas pour le cas de cet tache car il y a trop de combinaisons.
 
je continue a chercher

Reply

Marsh Posté le 01-04-2009 à 17:39:56    

Tu veux quoi?
 
La reponse numerique?  C'est un probleme de math que je n'aborderais pas par la programmation mais par l'analyse combinatoire.
 
Un moyen de generer facilement tous les arrangements (pour les combinaisons, par definition l'ordre n'a pas d'importance)?  Je partirais sur la technique utilisee pour generer les permutations que je modifierais pour generer les arrangements avec repetitions.  Mais c'est un probleme d'algorithmique et pas de C++.

Reply

Marsh Posté le 01-04-2009 à 17:53:16    

Merci de la reponse.
Je ne veux pas la reponse numerique puisque je peux la calculer par moi meme par analyse combinatoire comme tu l as explique.
L idee est de faire un programme arrivant au resultat sans attendre 5 minutes pour donner la reponse.
 
Je pense comme tu l as explique que c est plus un probleme d algo.
Si un modo peut envoyer le post en categorie algo
 
Bonne fin d aprem

Reply

Marsh Posté le 04-04-2009 à 14:42:56    

Raisonnons calmement (oh comme je me la pête :D) et laissons ce topic dans la catégorie C++ encore un peu SVP.
 
12 symboles (qu'importe que ce soit des chiffres) avec 10 symboles différents, interdit d'en avoir + de 3 identiques. Donc tous les ymboles doivent être présents, plus deux autres, différents entre eux.
 
Créons notre tableau de 12 symboles, rempli d'abord avec les 10 symboles :
 

Code :
  1. int tab[ 12 ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };


 
Je déclare une fonction output qui enregistrera un résultat. Elle pourrait enregistrer dans un fichier, par exemple. Qu'importe.
 

Code :
  1. void output( const int result[ 12 ] );


 
On va dérouler toutes les possibilités pour les deux symboles additionnels. Comme ce sont des nombres, on va utiliser comme critère de comparaison l'ordre strict des entiers, ça fera plaisir au CPU qui fait ça très bien (je reste à un niveau d'abstraction maximal).
 

Code :
  1. for ( int x = 0; x < 9; ++x )
  2. {
  3.     for ( int y = x + 1; y <= 9; ++y )
  4.     {
  5.         tab[ 10 ] = x;
  6.         tab[ 11 ] = y;
  7.     }
  8. }


 
Là le C++ entre en jeux. On va utiliser std::next_permutation pour dérouler toutes les combinaisons, pas besoin de faire 12 boucles imbriquées.
Il faut commencer avec le tableau trié, puis boucler sur les permutations :
 

Code :
  1. std::sort( tab, tab + 12 );
  2. do
  3. {
  4.     output( tab );
  5. }
  6. while( std::next_permutation( tab, tab + 12 ) );


 
Et c'est tout !!
Pour récapituler, voilà ce que ça donne :
 

Code :
  1. for ( int x = 0; x < 9; ++x )
  2. {
  3.     for ( int y = x + 1; y <= 9; ++y )
  4.     {
  5.         int tab[ 12 ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  6.         tab[ 10 ] = x;
  7.         tab[ 11 ] = y;
  9.         std::sort( tab, tab + 12 );
  11.         do
  12.         {
  13.             output( tab );
  14.         }
  15.         while( std::next_permutation( tab, tab + 12 ) );
  16.     }
  17. }

Reply

Marsh Posté le 05-04-2009 à 11:10:51    

Merci beaucoup Jesus_christ, tu es mon sauveur .... :)
 
Concernant le programme en lui meme:
 

Code :
  1. #include <iostream>
  2. using namespace std;
  4. int main(void)
  5. {
  6.     void output(const int result[ 12 ]) ;
  7. for ( int x = 0; x < 9; ++x )
  8. {
  9.     for ( int y = x + 1; y <= 9; ++y )
  10.     {
  11.         int tab[ 12 ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  12.         tab[ 10 ] = x;
  13.         tab[ 11 ] = y;
  15.         std::sort( tab, tab + 12 );
  17.         do
  18.         {
  19.             output(tab);
  20.         }
  21.         while( std::next_permutation( tab, tab + 12 ) );
  22.     }
  23. }


 
Ca ne compile pas car output n est pas definie, donc je dois definir la fonction
 

Code :
  1. void output(const int result[ 12 ])
  2. {
  3. }


 
Je veux juste que mon programme affiche la reponse a l ecran, et je ne comprend pas vraiment ce que je dois mettre dans la fonction output...
 
Merci de ton aide
 
 
 

Reply

Marsh Posté le 05-04-2009 à 15:21:27    

cout << ?
 
et surtout ne défini par la fonction dans le main, mais avant


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le 05-04-2009 à 15:21:27   

Reply

Marsh Posté le 05-04-2009 à 15:32:17    

{edit : j avais fais une erreur dans mon message}
 
Bon alors le soucis est le suivant, que mettre dans la fonction output?
Si je met un cout<<result[12], ca me ressort le meme nombre encore et encore a l ecran.
Si je lance le programme avec:

Code :
  1. void output(const int result[ 12 ])
  2. {
  3. }


 
Meme apres 5 minutes les programme tourne encore, je sais qu il ne devrait rien m afficher, mais il devrait au moins "terminer".
 
Merci de m aider, ca a l air de pas etre loin de la fin ...


Message édité par jeje87a le 05-04-2009 à 17:31:01
Reply

Marsh Posté le 05-04-2009 à 17:56:08    

Petites modifications:
 
J ai laissé tomber la fonction et j ai juste ajouter un compteur (f):

Code :
  1. #include <iostream>
  2. using namespace std;
  4. int main(void)
  5. {
  6. int f=0;
  7. for ( int x = 0; x < 9; ++x )
  8. {
  9.     for ( int y = x + 1; y <= 9; ++y )
  10.     {
  11.         int tab[ 12 ] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  12.         tab[ 10 ] = x;
  13.         tab[ 11 ] = y;
  15.         std::sort( tab, tab + 12 );
  17.         do
  18.         {
  19.             f=f+1;
  21.         }
  22.         while( std::next_permutation( tab, tab + 12 ) );
  23.     }
  24. }
  25.   cout<<f<<endl;
  26. return(0);
  27. }


 
Le programme compile en 500 secondes!
Des idées pour que cela soit plus rapide?
 
Si je veux étendre mon programme pour 16 chiffres dans le nombre comment puis je faire? (on atteind la limite de taille d un int ...)
Avec la methode de Jesus Christ ca passe mais au dela de 12...
 
Merci de votre aide

Reply

Marsh Posté le 05-04-2009 à 18:18:43    

J'avais pourtant dit :

Citation :

Je déclare une fonction output qui enregistrera un résultat. Elle pourrait enregistrer dans un fichier, par exemple. Qu'importe.


Ici ce n'est pas cette fonction qui doit poser problème, je te la code pour afficher si tu veux :
 

Code :
  1. void output( const int result[ 12 ] )
  2. {
  3.     for ( i = 0; i < 12; ++i )
  4.         std::cout << result[ i ];
  5.     std::cout << '\n';
  6. }


 
Le nombre de chiffre n'a rien à voir avec ceux affichage sur un int, ici tous les entiers sont de 0 à 9, on travaille sur des combinaisons de chiffres, pas des grands nombres à 12 chiffres, ne pas confondre. Si on travaillait sur des lettres de 'a' à 'j' ça serait exactement pareil.
 

Citation :

Le programme compile en 500 secondes!


Compile ????
Fonctionne tu veux dire ?
Déjà la fonction d'affichage risque d'être le goulot d'étranglement, et puis tu doit générer tellement de combinaisons que forcément ça ne se fait pas en 1s. Avec ton compteur f il n'y a plus ce problème normalement, es-tu sûr de compiler en mode release, c'est à dire optimisé ?
Sans ça les perfs sont forcément mauvaises.

Reply

Marsh Posté le 05-04-2009 à 18:28:41    

Désolé Jesus Christ, je perd un peu de lucidité a force de chercher.
 
Désolé pour le cout de la fonction qui affiche...  
Ce qui au final m interesse c est juste le compteur comme dans le code "final" que j ai ecrit.
 
Le prgramme compile en 1sec pas en 500, erreur de vocabulaire, mea culpa. Je compile avec codeblocks, mais ce ne change rien a l exe au final, si?
Le programme fonctionne mais 500 sec pour trouver le nombre de possibilites c est un peu long en effet, tu peux essayer le code sur ton pc si tu le souhaites et me dire si cela est plus rapide...
 
La ou je parle de soucis c est que mon compteur ne peut depasser la limite de long, et donc si je fais le meme programme pour 16 chiffres dans le nombre par exemple, il y aura trop de possibilités pour le compteur, a mois d ecrire le compteur sous forme de tableau pour eviter tout probleme et afficher le tableau final a la fin ...
 
Pourrais tu, s il te plait, me donner le début du code si on prend 16 chiffres par exemple. Chaque ajout de chiffre implique un ajout de boucle non? donc au lieu de 2 boucles aura t on 6 boucles?
 
merci de votre patience
 
{edit} j ai tenté d ajouter une ligne pour 13 chiffres (une 3eme boucle avec un z et un changement sur tab), le programme tourne ... la reponse dans moins d une heure j espere


Message édité par jeje87a le 05-04-2009 à 19:04:08
Reply

Marsh Posté le 05-04-2009 à 19:08:35    

ok je vais l'écrire chez moi et je te donne les perfs, j'ai un CPU à 2000Mhz pour info, je te dis ça.

Reply

Marsh Posté le 05-04-2009 à 19:10:43    

Merci  :jap:  
 
Pour ma part, core duo 2ghz.
Le programme avec une troisieme boucle tourne depuis environ 10min

Reply

Marsh Posté le 05-04-2009 à 19:20:10    

chez moi aussi, même en Release, c'est très long, mais quand j'y repense, avec 10^12 combinaisons au total, avec un cpu à 2GHz ça fait, même si chaque essai prenait 1 cycle, 500 secondes justement. Or on ne peut pas tester + d'une combinaison par cycle, et en pratique chaque test prend de nombreux cycles, donc 500s ça me parait déjà assez optimisé.
 
pour 16 chiffres d'ailleurs il y aura un débordement pour le compteur f.

Reply

Marsh Posté le 05-04-2009 à 19:28:34    

Donc malheureusement tu ne penses pas qu il soit possible de descendre sous les 2 ou 3 minutes avec 16 chiffres.
 
Merci d avoir prit du temps pour m expliqué tout ca.
Je vais devoir trouver une autre solution, ne pas calculer toutes les possibilités mais juste avoir un programme qui donne le resultat sans passer par la case calcul.
Je sais deja qu en theorie j ai 10^16 possibilites, j en ai moins que ca en posant un min et un max, et en sachant qu aucun nombre commencant par 0 n est possible.
 
Je vais essayer de trouver un livre de math combinatoire pour trouver la reponse.
Avec 9 chiffres, pas de debut en 0, pas de doublon la reponse est 9x9! par contre avec 16 chiffres et les conditions posees, je ne sais pas trop comment m y prendre.
 
Meme si j arrive a trouver la reponse mathematiquement, je pourrais essayer d appliquer le raisonement en c++.  
Partant du nombre maxi, puis appliquant les conditions et dire, j enleve tel nombre de possibilites ...
 
qu en pensez vous?

Message cité 1 fois
Reply

Marsh Posté le 05-04-2009 à 19:39:26    

jeje87a a écrit :

Donc malheureusement tu ne penses pas qu il soit possible de descendre sous les 2 ou 3 minutes avec 16 chiffres.
 
Merci d avoir prit du temps pour m expliqué tout ca.
Je vais devoir trouver une autre solution, ne pas calculer toutes les possibilités mais juste avoir un programme qui donne le resultat sans passer par la case calcul.
Je sais deja qu en theorie j ai 10^16 possibilites, j en ai moins que ca en posant un min et un max, et en sachant qu aucun nombre commencant par 0 n est possible.


 
1) A moins de précalculer, ce qui serait un peu de la triche, trouver un résultat sans le calculer, c'est de l'informatique quantique, et ça n'existe pas encore, si ça existe un jour :D
2) Pourquoi le zéro de départ est-il interdit ?
Tu avais dit :

Citation :

Je cherche le nombre de combinaison possible de 12 chiffres utilisant les chiffres de 0 a 9.


Ca n'interdit pas de commencer par zero.

Reply

Marsh Posté le 05-04-2009 à 19:58:17    

Desole Jesus Christ, je m'embrouille.
 
Mon probleme est en 2 partie:
- solution avec 12 chiffres dans le nombre, de 0 a 9, pas plus de 3 fois chaque chiffre
- solution avec 16 chiffres dans le nombre, de 0 a 9, pas plus de 3 fois chaque chiffre et pas de 0 au debut du nombre (ca enleve une puissance de 10 en possibilites).
 
Je parlais de "pre calculer", a savoir utiliser des resultats connus, j admet que c est tricher mais si il n ai pas "physiquement" possible de trouver le resultat en 2 ou 3 minutes (du au trop grand nombre de possibilites) je vais devoir trouver une autre solution.
 

Reply

Marsh Posté le 05-04-2009 à 20:17:10    

Le fichier dans lequel serait enregistré les solutions risque de faire plusieurs Gigas.
Interdir le zéro au début ne fera passer les combinaisons que de 10^16 à 9*10^15.

Reply

Marsh Posté le 05-04-2009 à 20:22:58    

Je ne veux pas enregistrer les solutions, juste la reponse.
 
C est pour cela que j avais introduit uniquement un compteur dans mon programme.
Je veux juste la solution qu importe la méthode :), tant que c est en c++ ;)


Message édité par jeje87a le 05-04-2009 à 20:23:18
Reply

Marsh Posté le 05-04-2009 à 20:31:09    

ah, juste le nombre de solutions !
Dans ce cas ça peut se calculer formellement, mais c'est des maths à coup de factorielles et compagnie, ce n'est pas de la programmation.

Reply

Marsh Posté le 05-04-2009 à 21:20:45    

On est bien d accord.
 
D ou mon probleme, on me demande de résoudre le probleme grace a la programmation en mois de 3 minutes.
Il semble si je t ai bien comprit qu il ne soit pas possible de résoudre ce probleme en moins de 3 minutes, n est ce pas?
 
C est pourquoi je dois avouer etre un peu confu.
 

Reply

Marsh Posté le 07-04-2009 à 11:28:59    

Bah tu calcule à la main avec des maths, et puis cout << resultat << "\n"; nan ?
 
Calculer le nombre de solutions ne consiste pas forcément à compter les solutions  :o


---------------
You can't start a fire with moonlight
Reply

Marsh Posté le 06-05-2009 à 11:00:25    

jeje87a a écrit :

Bonsoir a tous
 
J ai un soucis concernant un casse tete pour lequel je ne parviens pas a trouver de solution.
 
Je cherche le nombre de combinaison possible de 12 chiffres utilisant les chiffres de 0 a 9. J ai donc 10^12 possibilitees.


Ben voilà tu as déjà trouvé la réponse dans le premier post !


---------------
What if I were smiling and running into your arms? Would you see then what I see now?  
Reply

Marsh Posté le    

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed