trouver le n° d'une combinaison sur 13983816 ??

[invite6b72ac19]

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

[invitea3eb043e]

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.

[yat]

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!).

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...

[invite6b72ac19]

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 ?

[A voir en vidéo sur Futura]

[invité576543]

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,

[yat]

comment obtenir le numéro de solution d'une combinaison donnée dans mon exemple 9-17-27-35-44-48

C'est 9 936 370

Ma deuxiéme question est cette formule existe t-elle ?

D'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...

#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

(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.)


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...

[invité576543]

...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).

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,

[invité576543]

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,

[invité576543]

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+1, 5).

Ca a une forme fermée parce que C(5+i, 5) est un polynome en i de degré 5. Suffit de faire les sommes par puissance...

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,

[invite6b72ac19]

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,

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

[invité576543]

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,

[invite6b72ac19]

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

[invite6b72ac19]

#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...

Bravo le résultat est bon, saurais tu yat comment réecrire ta fonction pour easyphp ?