Discussion :

[zhao]

Bonjour a tous :-)
je dis pour les experts car cela ne me semble pas evident .
voila le probleme a resoudre ,je souhaiterais generer toutes combinaisons de N parmi K ( en realité N varie de 25 a 90 et K de 4 a 25 et il est la mon probleme)
prenon l'exemple du loto que vous connaissez bien le programme pour generer les combis est tres simple sous devcpp)
je debute en programmation sous devcpp

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include<stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <time.h>
 
 
main()
{
int zz=0,a=0,i=0,j=0,k=0,l=0,m=0,n=0,tc[6],touche=0;
int nt=0;
 
printf("entrez votre valeur ");
scanf("%d",&nt);
 
a=nt-5;
 
for(i=1;i<=a;i++)
for(j=i+1;j<=a+1;j++)
for(k=j+1;k<=a+2;k++)
for(l=k+1;l<=a+3;l++)
for(m=l+1;m<=a+4;m++)
for(n=m+1;n<=a+5;n++)
{
 
tc[0]=i;tc[1]=j;tc[2]=k;tc[3]=l;tc[4]=m;tc[5]=n;
printf("%d %d %d %d %d %d \n",tc[0],tc[1],tc[2],tc[3],tc[4],tc[5]);
zz++;
 
 
}
printf("nombre de combinaisons %d ",zz);
scanf("%d",&touche);
getchar();
}

maintenant comme mes valeurs contrairement au loto varie je suis obliger de changer le code a chaque fois ,de plus si k = 20 par exemple cela m'oblige a creer 20 boucles imbriquées alors voici ma question :
je sais qu'il est possible d'eviter toutes ses boucles en creant ce qu'on appelle une boucle dynamique donc en theorie avec une seule boucle il est possible de sortir toutes les combinaisons de N parmi K ( ou l'inverse je ne me souviens plus de la formulation mais bon vous aurez compris ;-) )
supposons que je veuille sortir toutes les combinaisons de 15 chiffres parmi 70 cela m'oblige a creer 15 boucles bref et a chaque fois je doit allez dans mon programme pour changer les valeurs bref pas evident ( en tous cas pour moi ;-) )
pouvez vous m'aider ?

prenon cet exemple :
avec le petit programme que j'ai poster plus haut si je donne a "NT" la valeur 8 je vais avoir toutes les combinaisons de 6 chiffres parmi 8
donc
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
1 2 3 4 6 7
.........
.........
3 4 5 6 7 8

j'ai pris l'exemple du loto car pour les combinaisons c'est ce qui me semblais le plus parlant pour un francais ;-)
mais si par exemple je veux generer toutes les combinaisons de 10 chiffres parmi 50 je suis obliger de changer mon code et faire 10 boucles , voila il est la mon probleme comment generer toutes les combinaisons de X parmi Y quelque soit X et Y sans etre obliger de changer mon code a chaque fois ,je crois qu'il est possible de faire cela avec une seule boucle qu'on nomme boucle dynamique bref pouvez vous m'aider ?

cordialement

[Jean-Marc.Bourguet]

En quoi les deux liens que je t'ai donné dans le forum C ne te conviennent pas?

[zhao]

ce n'est pas qu'il ne me convienne pas mais il y en a un que je ne peut pas lire ( je sais pas pourquoi) et l'autre je vois pas comment il peut resoudre mon probleme desolé mais n'oublie pas que je suis un neophite en programmation j'arrive pas a comprendre comment ce lien peut m'oter toutes mes boucles si tu veux m'expliquer avec du code "peut etre" que je comprendrais ;-)
cordialement

[zhao]

En quoi les deux liens que je t'ai donné dans le forum C ne te conviennent pas?

prenons ton exemple sur ce lien que tu m'as fourni :
http://www.developpez.net/forums/sho...04&postcount=5

j'arrive pas a comprendre comment ce programme peut resoudre mon probleme peut etre parce que c'est pas du C mais j'ai quand meme un doute ( le doute viens de mon ignorance et non pas de ton code )
cordialement

[sovitec]

As tu calculé quand même que C(90,25) = 11613412635260273974818.

Même en en générant 100 000 000 par seconde (optimiste) cela prendra plus de 3 millions d'années !

[j.p.mignot]

Et encore pire si on parle d' A(n,p) !

[Jean-Marc.Bourguet]

prenons ton exemple sur ce lien que tu m'as fourni :
http://www.developpez.net/forums/sho...04&postcount=5

j'arrive pas a comprendre comment ce programme peut resoudre mon probleme peut etre parce que c'est pas du C mais j'ai quand meme un doute ( le doute viens de mon ignorance et non pas de ton code )
cordialement

Ce message explique comment faire un nombre variable de boucles imbriquées. Il te suffit d'appliquer la technique à ton problème.

[syl20dies]

Bonjour je me suis intéressé à ce topic, tant pour la génération de combinaisons que plus généralement pour simuler le comportement de n boucles for imbriquées.

étant plus bidouilleur que developpeur, j'y suis parvenu dans le cas présent en développant la fonction suivante (en AS2), aussi si une personne expérimentée avait la patiente de l'examiner, je serait vivement intéressé par toute suggestion et/ou recommandation d'optimisation.

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
function combi(arr_in,n){
    /*retourne un tableau contenant sur chaque indice, un tableau contenant n elements du tableau passé en paramètre et constituant une combinaison unique de n parmis arr_in*/
    comb=[];
    fini=false;
    id=Array(n);
    for(cptid=0;cptid<n;cptid++){id[cptid]=cptid;}
    id[n-1]=id[n-1]-1;
    while(!fini){
        exit=false;
        for(i=n-1;i>=0 && !exit;i--){
            if(id[i]<arr_in.length-n+i){
                id[i]++;
                exit=true;
            }else{
                fini=(i==0);
                first=true;
                for(cpt=(n-i);cpt>0;cpt--){
                    id[n-cpt]=id[(n-1)-cpt]+((first)?2:1);
                    first=false;
                }
            }
        }
        if(!fini){
            arr_aux=Array(n);
            for(cptid=0;cptid<n;cptid++){arr_aux[cptid]=arr_in[id[cptid]];}
            comb.push(arr_aux);
        }
    }
    return comb;
}