Bonjour je ne me souviens pas avoir vu ca en cours et j'ai besoin de connaitre la formule qui permet de connaitre le numéro de solution d'une combinaison qui va de 1 a 13983816 ?
je m'explique avec un exemple (LOTO) :
la 1er solution c'est => 1-2-3-4-5-6
la 2eme => 1-2-3-4-5-7
Ma question est quel calcul faut il effectuer dans ce cas pour connaitre le n° de solution de ma combinaison => 9-17-27-35-44-48 ?
merci d'avance
Me paraît délicat.
En effet, on peut imaginer qu'on écrit les combinaisons comme tu fais :
1 2 3 4 5 6 puis
1 2 3 4 5 7 etc..
ensuite on change l'avant dernier chiffre, et on remet ça.
Problème : on va obtenir 120 fois chaque combinaison (6!).
La combinaison que tu donnes en exemple a été remise dans l'ordre croissant. Donc il faut regarder quand elle a été obtenue pour la première fois sur les 120.
Envoyé par Jeanpaul
Je ne pense pas que tu aies compris le truc. Il s'agit d'incrémenter le numéro qui se trouve le plus à droite possible. Et si le numéro incrémenté n'est pas celui de droite, on remet ceux qui sont à sa droite "à zéro", en respectant le fait que les combinaisons sont toutes présentées dans l'ordre.
Par exemple, après 1 2 3 47 48 49, on aura 1 2 4 5 6 7.
Pour la question initiale, je n'ai pas trop d'idée...
Merçi de vos réponses
Sachant que pour connaitre le nombre de possibilité total
on fait (44*45*46*47*48*49) / (1*2*3*4*5*6)
ce qui donne 10068347520 / 720 = 13983816 possibilité
je me disais donc si une formule comme celle ci dessus permet de connaître le nombre de possibilité total, peut-etre peut-on faire de même pour mon probléme et j'ai essayé cette formule dans tous les sens mais sans trouver comment obtenir le numéro de solution d'une combinaison donnée dans mon exemple 9-17-27-35-44-48
Ma deuxiéme question est cette formule existe t-elle ?
Bonjour,
Si je comprend bien tu veux numéroter 1 la combinaison 1-2-3-4-5-6, 2 la combinaison 1-2-3-4-5-7, etc jusquà 13983816 comme numéro de 44-45-46-47-48-49 ?
J'avais eu le problème à résoudre dans le temps, pour numéroter des ensembles de fréquences dans un message du GSM.
Je me rappelle qu'il y a une formule, j'avais une publication, elle doit être enterrée loin dans mes archives. (La solution que j'ai proposée et qui a été adoptée dans le standard n'est pas cette numérotation, qui serait le codage optimal, pour des raisons de temps de calcul...).
Donc la seule information que je te donne est que la formule existe. Ca doit se retrouver, c'est à grands coups de C(n, p)...
Cordialement,
C'est 9 936 370D'après mmy, il y en a une.
Personnellement je vois pas comment aboutir... alors quand je sais pas, je commence par la méthode bète... ça t'aidera peut-être pas, mais...
(Ce code a déjà le bon gout de me donner 0 pour la combinaison 1 2 3 4 5 6 et 13 983 815 pour la combinaison 44 45 46 47 48 49.)Code:#include <stdio.h> #include <conio.h> void suivante(int temp[6]){ int i; i=5; while(temp[i]==(49+i-5)) i--; temp[i]++; i++; while(i<6){ temp[i]=temp[i-1]+1; i++; }//while }//suivante int compare(int comb[6],int temp[6]){ int i; for(i=0;i<6;i++) if(comb[i]!=temp[i]) return (0); return(1); }//compare int compte(int comb[6]){ int temp[6]; int res; int i; for(i=0;i<6;i++) temp[i]=i+1; res=0; while(compare(comb,temp)==0){ suivante(temp); res++; }//while return(res); }//compte void main(void){ int comb[6]; int i; int res; for(i=0;i<6;i++){ printf("numero %i ?\n",i+1); scanf("%d",&(comb[i])); }//for res=compte(comb); printf("Combinaison numero %d\n",res); getch(); }//main
Après on peut tenter le coup de manière un peu moins violente...
Prenons par exemple 4 6 7 8 9 10. Avant d'arriver à cette combinaison, on aura du passer toutes celles qui commencent par 1, 2 et 3. On peut les dénombrer facilement, puisque ça revient à fixer le premier numero et à dénombrer les combinaisons de 5 numéros supérieurs.
On en a donc 1 712 304 pour le 1, 1 533 939 pour le 2 et 1 370 754 pour le 3. On peut donc en déduire que le numéro de la combinaison 4 5 6 7 8 9 est 4 616 997. Déjà à ce stade là, disposer d'une formule qui donne le truc en un coup ça aiderait.
Ensuite, pour aller jusqu'à notre combinaison, il a encore fallu passer toutes celles qui commencent par 4 et dont le deuxième chiffre est 5. Ca revient à calculer les combinaisons de 4 chiffres entre 6 et 49, il y en a 135 751. Le numero de notre combinaison est donc 4 752 748. Cool, c'est ce que me donne mon programme avec une méthode complêtement différente.
Ce qui m'a donc permis de me servir de mon programme pour trouver que le numéro de ta combinaison est 9 936 369, soit 9 936 370 si on commence la numérotation à 1.
...bon, maintenant, c'est sur que s'il y a une formule...
Ce que je disais était de mémoire! Le travail auquel je faisais allusion date du début des 90'. Le problème est que je peux faire une confusion entre une formule fermée et un algo un tant soit peu efficace (plus que le tien, mais ce n'est pas dur)....bon, maintenant, c'est sur que s'il y a une formule...
Pour le premier chiffre on se trouve devant une somme de C(50-i, 5). Ces machins là s'approchent (il me semble) par la fonction intégrale de e-x² (c'est quoi son nom, d'ailleurs? Panne de mémoire...), et toute formule approchant mieux que l'unité permettra par troncature de trouver le numéro. Par récurrence sur les chiffres successifs on obtient quelque chose...
Cordialement,
Dernière modification par invité576543 ; 11/10/2006 à 14h06.
En réfléchissant un peu, c'est plus simple en partant à l'envers, et le problème est celui du calcul de somme(i=0, i=n) de C(5, 5+i).
Ca a une forme fermée parce que C(5, 5+i) est un polynome en i de degré 5. Suffit de faire les sommes par puissance...
Voilà... Je laisse les détails à qui veut...
(Pouvez oublier mon messages précédents, c'était n'importe quoi...)
Cordialement,
C'est encore plus simple que ça... (On va y arriver)
somme(i=0, i=n) de C(5+i, 5) = C(n+6, 6)
La numérotation en commençant à l'envers (0 pour 44-45-46-47-48-49) est quelque chose comme
C(49-k1, 6) + C(49-k2, 5) + C(49-k3, 4) + C(49-k4, 3) + C(49-k5, 2) + C(49-k6, 1)
A quelques erreurs d'indiçage, ça doit être quelque chose comme ça...
Cordialement,
Bravo le résultat est bon, saurais tu yat comment réecrire ta fonction pour easyphp ?Code:#include <stdio.h> #include <conio.h> void suivante(int temp[6]){ int i; i=5; while(temp[i]==(49+i-5)) i--; temp[i]++; i++; while(i<6){ temp[i]=temp[i-1]+1; i++; }//while }//suivante int compare(int comb[6],int temp[6]){ int i; for(i=0;i<6;i++) if(comb[i]!=temp[i]) return (0); return(1); }//compare int compte(int comb[6]){ int temp[6]; int res; int i; for(i=0;i<6;i++) temp[i]=i+1; res=0; while(compare(comb,temp)==0){ suivante(temp); res++; }//while return(res); }//compte void main(void){ int comb[6]; int i; int res; for(i=0;i<6;i++){ printf("numero %i ?\n",i+1); scanf("%d",&(comb[i])); }//for res=compte(comb); printf("Combinaison numero %d\n",res); getch(); }//main
...bon, maintenant, c'est sur que s'il y a une formule...
je m'excuse de mon niveau médiocre mmy, mais pour comprendre ce que tu donne, je dois proceder comme ça : C(49-9, 6) + C(49-17, 6) + C(49-27, 6) + (49-35, 6) + (49-44, 6) + (49-48, 6) ?
merci mmy
Non, mais
13983816 - [ C(49-9, 6) + C(49-17, 5) + C(49-27, 4) + (49-35, 3) + (49-44, 2) + (49-48, 1) ]
Ce sous réserve de vérification de la formule, je n'ai pas le temps de le faire, c'est juste une indication par l'exemple d'un raisonnement possible.
Si par hasard ça donne le bon numéro du premier coup, on pourra applaudir, mais le plus vraisemblable est qu'il y a des erreurs, des +1 par ci ou des -1 par là...
Cordialement,
Encore désolé je n'y arrive pas !
je fait :
C(49-9, 6) => (40*40*40*40*40*40) soit 4096000000
C(49-17, 5) => (32*32*32*32*32) soit 33554432
C(49-27, 4) => (22*22*22*22) soit 234256
C(49-35, 3) => (14*14*14) soit 2744
C(49-44, 2) => (5*5) soit 25
C(49-48, 1) => (1) soit 1
mais là j'obtient 4129791458 et donc ce resultat est plus grand que 13983816, je m'y suis encore mal pris ?
je me demande si C(49-9, 6) veut bien dire 49-9 donc (40*40*40*40*40*40)
Merci de ta patience mmy
Cordialement
Je peux faire une suggestion ? (si c'est débile, tapez très fort
Je me demande si la formule dont parle mmy n'aurait pas un rapport avec les nombres de Catalan...
A quitté FuturaSciences. Merci de ne PAS me contacter par MP.
Non, c'est 40*39*38*37*36*35
Mais j'ai juste jeté quelques idées... Rien ne dit que ce que je propose est correct. Vaudrait mieux refaire le raisonnement...
Sinon, ça ne devrait pas dépasser, le nombre le plus grand c'est
C(48, 6) + C(47, 5) + C(46, 4) + C(45, 3) + C(44, 2) + C(43, 1)
Ca devrait rester sous (en fait égal à 1 près), à C(49, 6)
Bonne vérification à faire... Mais je ne suis pas Yat, je ne programme pas plus vite que mon ombre, je fais tout à la main ou presque!
Cordialement,
J'ai fait la vérif pour la combi 1-2-3-4-5-6, ça marche
Et j'ai fait l'autre vérif, ça marche aussi
Ca doit être la bonne formule, donc...
Cordialement,
Bonjour j'en suis resté là hier soir
C(49-9, 6) => (40*39*38*37*36*35) soit 2763633600
C(49-17, 5) => (32*31*30*29*28) soit 24165120
C(49-27, 4) => (22*21*20*19) soit 175560
C(49-35, 3) => (14*13*12) soit 2744
C(49-44, 2) => (5*4) soit 20
C(49-48, 1) => (1) soit 1
! 2 787 977 045
Encore le resultat plus grand que 13983816, je n'y comprends pas grand chose ?
Cordialement
Juste un détail qui cloche : C(40,6), ça fait 40*39*38*37*36*35/(6*5*4*3*2*1).
Ca devrait mieux marcher comme ça
d'accord merci mmy, j'avais egalement essayé hier soir mais j'ai laissé de coté car j'obtenais :
(40*39*38*37*36*35) / (6*5*4*3*2*1) = 3838380
(32*31*30*29*28) / (6*5*4*3*2*1) = 33562,67
(22*21*20*19) / (6*5*4*3*2*1) = 243,83
(14*13*12) / (6*5*4*3*2*1) = 3,81
(5*4) / (6*5*4*3*2*1) = 0,03
(1) / (6*5*4*3*2*1) = 0
total 13983816-3872190,34 = 10111625,66
c'est pour cela que je n'ai pas continuer dans cette direction on doit trouver 9 936 370 et j'ai 10111626
qu'en pense tu mmy ?
cordialement
Oui, alors encore un détail :
C(32, 5) => (32*31*30*29*28)/(5*4*3*2*1)
L'indice qui peut te mettre sur la voie, c'est que C(n,p), avec n et p entiers, ça fait forcément un nombre entier
Pour finir :
C(49-9 , 6) => (40*39*38*37*36*35)/(6*5*4*3*2) = 3838380
C(49-17, 5) => (32*31*30*29*28)/(5*4*3*2) = 201376
C(49-27, 4) => (22*21*20*19)/(4*3*2) = 7315
C(49-35, 3) => (14*13*12)/(3*2) = 364
C(49-44, 2) => (5*4)/2 = 10
C(49-48, 1) => 1 = 1
total 4047446
13983816-4047446=... gagné !La formule de mmy est donc bonne du premier coup, sans le moindre petit +1 ou -1 par ci par là.
Bonjour,
J'arrive après la bataille... Merci pour la vérif indépendante! Voilà une question réglée, il semble!
Cordialement,
Effectivement mon probléme est réellement résolu.
Je vous remercie tous deux pour votre contribution, qui va me permettre de supprimer ma table (mysql) qui contenais les 13983816 de combinaisons soit env 700Mo sur le disque dur, et des requetes assez longue, alors que là avec cette formule je vais concocter une fonction php, certainement bien plus rapide et qui n'utilise pas une énorme table d'environ 700Mo.
Je reste cependant étonné du serieux et du temps de réaction qui dépasse ce que je connaissais sur d'autres forum.
Je peux rajouter une chose ceux qui goûtent a ce forum risque de l'apprecier énormement, c'est mon cas.
Je vais finir mon dev et je vais revenir voir ou est-ce que je peux a mon tour contribuer a en aider d'autre, encore merci yat et mmy.
mille merçi de votre efficacité et serieux !
je me rend compte que je me suis emballé un peu vite
en effacent la table qui contenais les combinaisons, je m'aperçois d'un hic, comment retrouver la combinaisons a partir du numéro de solution ?
c'est vrai que je n'ai pas pensé a la fonction inverse !
pauvre de moi
Suffit de tabuler les 44 C(49-k, 6), les 44 C(49-k, 5), etc... soit moins de 300 valeurs.je me rend compte que je me suis emballé un peu vite
en effacent la table qui contenais les combinaisons, je m'aperçois d'un hic, comment retrouver la combinaisons a partir du numéro de solution ?
c'est vrai que je n'ai pas pensé a la fonction inverse !
pauvre de moi
Ensuite l'algo consiste à trouver le C(49-k, 6) juste inférieur, ça donne k1, puis faire la différence, et continuer avec le suivant, etc.
Cordialement,
Tu peux retrouver les uméros les uns après les autres : D'abord tu soustrais ton indice à 13983816 pour retomber sur la numérotation originale.
Ensuite, tu calcules C(49-i,6) en partant de 1 et jusqu'à ce que tu dépasses la valeur de l'indice. i-1 sera le premier numéro. Tu soustrais C(49(-i-1),6) de l'indice, et tu recommences avec C(49-i,5) pour retrouver le deuxième numéro, etc...
EDIT : croisement avec mmy... oui, ou alors avec une table, ça peut aller plus vite.
Le calcul des C(49-i, 6) successifs est assez facile, effectivement, on a
C(49-i-1, 6) = C(49-i, 6) (43-i)/(49-i)
2 add, 1 mul, 1 div à chaque coup, pas trop lourd!
Ca ne mérite pas une table...
Cdlt
Dernière modification par invité576543 ; 12/10/2006 à 16h16.
d'accord en reprenant le même exemple c'est plus simple avec 9936370 pour 9-17-27-35-44-48 :
donc 4047446, et hop je bloque a nouveau !
C(49-?, 6) => (49*48*47*46*45*44) (43-i) =
En fait faut commencer avec i=43, on a
C(49-43, 6) = 1
ensuite C(49-42, 6) = 1 x 7/1 = 7
ensuite C(49-41, 6) = 7 x 8/2 = 28
ensuite C(49-40, 6) = 28 x 9/3 = 84
Jusqu'à ce qu'on dépasse... Ca donne le premier nombre, on fait la différence, et on recommence avec 5 à la place de 6, etc.
Cordialement,
Le faire dans le sens croissant va en fait plus vite, statistiquement, mais c'est de l'optimisation par un facteur...
On commence avec C(48,6) = 12271512, puis on a C(47,6) = C(48,6) 42/48, etc.
On boucle jusqu'à ce que soit plus petit, ...
Ca va plus vite parce qu'on prend les grands nombres avant les petits... et on n'a pas à mémoriser le précédent...
Cordialement,
je ne te cache pas que de cet maniére j'ai du mal.
mmy peut tu m'indiquer de cet maniére stp,
(48*47*46*45*44*43) =
car je bloque encore, le plus simple peut etre c'est de me le presenter comme l'as fait yat, de cette maniére je comprends du premier coup, merci
cdt
