Calcul de toutes les combinaisons de N parmi K

**zhao** · 24/10/2006, 03h09

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)

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 ?
cordialement

**Interruption13h** · 24/10/2006, 07h18

Salut !

Envoyé par zhao

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

Je doit dire que j'ai pratiqument rien compris de ce que tu veux faire

Et ton code n'est pas très claire (Faut donner un nom significatif aux variables) !

en tout les cas, la combinaison me fais rappeler la formule :Combinaison(K,N)= N!/(K!*(N-K)!)

Si tu veux bien donner un exemple concré de ce que tu veux, pour pouvoir essayer de t'aider.

Bonne chance !

(Esque'il faut que je sois un expert pour comprendre ?

)

**Jean-Marc.Bourguet** · 24/10/2006, 09h26

Ça me semble être une question d'algorithmique, pas de C. Demande qu'on déplace le sujet.

La récursivité peut t'aider. Je dois avoir expliqué cela en détail dans ce forum (celui de C), il n'y a pas si longtemps.

Voir aussi http://www-cs-faculty.stanford.edu/~knuth/fasc3a.ps.gz pour plus de choses que tu n'en désires peut-être.

**Franck.H** · 24/10/2006, 10h11

Déjà s'il y'a de la factorielle dans l'air, le mieux est d'opter pour de la récursivité. J'en ai écrit un petit tutoriel y'a pas si longtemps, si ca peut aider: Récursivité en Langage C

**zhao** · 24/10/2006, 10h23

merci pour vos reponses :-)

bon deja je suis pas sur que la recursivité peut resoudre mon probleme mais si c'est le cas je suis preneur .

ensuite pour Interruption13h voici un 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** · 24/10/2006, 10h34

Envoyé par zhao

bon deja je suis pas sur que la recursivité peut resoudre mon probleme mais si c'est le cas je suis preneur .

http://www.developpez.net/forums/sho...04&postcount=5

**Interruption13h** · 24/10/2006, 13h15

Salut !

Envoyé par zhao

merci pour vos reponses :-)

bon deja je suis pas sur que la recursivité peut resoudre mon probleme mais si c'est le cas je suis preneur .

ensuite pour Interruption13h voici un 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

Et le 876543 ,222222 ? autrement dis ,esque c'est une combinaison répétitif ?

Je suis pas français et j'ai jamais joué au loto

A+

**zhao** · 24/10/2006, 13h27

repetitif ? be non jai mis un exemple plus haut avec 8 numeros ou alors je me suis mal exprimer ,si par exemple NT=7 alors j'aurais comme resulat de 6 parmi 7 ceci et uniquement ceci :

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

cela est plus simple que des explication ou je suis capable de dires des anneries ;-)

**Jean-Marc.Bourguet** · 24/10/2006, 13h31

Envoyé par Interruption13h

Et le 876543 ,222222 ? autrement dis ,esque c'est une combinaison répétitif ?

Les répétitions ne sont pas autorisées et l'ordre n'a pas d'importance.

**Interruption13h** · 24/10/2006, 13h54

Re !

Si j'ai bien compri,si on prend l'exemple de N=100 chiffres,la combinaison de K=6 serai :

95 96 97 98 99 100
94 96 97 98 99 100
93 96 97 98 99 100
.
.
1 96 97 98 99 100
1 95 97 98 99 100
.
.
1 2 97 98 99 100
1 2 96 98 99 100
.
.
.
.
1 2 3 4 5 6

?

Si c'est ça,je croi que c'est possble de faire que 3boucles suffisantes pour tout N et K (K<=N)

Alors ?

A+

**zhao** · 24/10/2006, 14h00

si j'ai bien compris ce que tu as poster oui c'est cela mais en commencant par 1 2 3 4 5 6
....
....

et la derniere sera bien sur

95 96 97 98 99 100

si quelque soit N et K tu fais ca en 3 boucles et bien cela serais genial ;-)

car supposons en prenant ton exemple au lieu de 6 ce soit je sais pas moi dions 45 tu imagine avec ma methode je suis obliger de faire 45 boucles alors 3 c'est le reve ;-)

je programme ( enfin que je dit programme disons plutot que je galere) en c sous devcpp ;-)

**Interruption13h** · 24/10/2006, 14h25

Voila :

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
 
#include<stdio.h>
 
 
int NbrCombinaisaon, K;
 
void Affichier_Combinaison(int* UneCombinaison)
         {
         int indice;
         NbrCombinaisaon++;/*mise à jours du nombre de combinaison*/
         for(indice=0;indice<K;indice++)
               {
               printf("%d ",UneCombinaison[indice]);
               }
          printf("\n");
         }
void main(int argc, char* argv[])
{
int N,indice;
int UneCombinaison[100];
 
/*******************Sasie********************/
printf("entrez votre valeur N ");
scanf("%d",&N);
 
printf("entrez votre valeur K ");
scanf("%d",&K);
 
 
 
//Vérification de la saisie ...!!!!!!!! à toi :D
 
 
 
 
 
 
/*remplir le tableau par la plus grande valeur possible comme je t'ai montré dans l'exemple :       */
 
for(indice=K;indice>=0;indice--)
       {
       UneCombinaison[indice]=N-(K-indice) ;
       }
 
 
 
 
 
 
NbrCombinaisaon=0;/*initialisation du nombre de combinaison !
 
 
 
 
/*Affichier les autres*/
for(indice=0;indice<K;indice++)
      {
       while(UneCombinaison[indice]>indice+1)
              {
               UneCombinaison[indice]--;
               Affichier_Combinaison(UneCombinaison);
              }
 
      }
 
 
 
 
printf("nombre de combinaisons %d ",NbrCombinaisaon);
 
getch();
}

Alors c'est bon ? ça fait 3 boucle

++

**Trap D** · 24/10/2006, 14h34

Avec des globales

**Interruption13h** · 24/10/2006, 14h51

Envoyé par Trap D

Avec des globales

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
 
 
 
#include<stdio.h>
 
void Affichier_Combinaison(int* UneCombinaison,int K)
         {
         int indice;
 
         for(indice=0;indice<K;indice++)
               {
               printf("%d ",UneCombinaison[indice]);
               }
          printf("\n");
         }
 
 
 
 
 
void main()
{
int N,indice,NbrCombinaisaon,K;
int UneCombinaison[100];
printf("entrez votre valeur N ");
scanf("%d",&N);
 
printf("entrez votre valeur K ");
scanf("%d",&K);
 
 
 
//Vérification de la saisie ...
 
 
 
/*Déclarration de ton tableau UneCombinaison qui contien K élément de type int (dynamiquement su c'est possible) */
 
 
 
/*remplir le tableau par la plus grande valeur possible comme je t'ai montré dans l'exemple :       */
for(indice=K;indice>=0;indice--)
       {
       UneCombinaison[indice]=N-(K-indice) ;
       }
Affichier_Combinaison(UneCombinaison,K);
 
NbrCombinaisaon=0;/*initialisation du nombre de combinaison !
 
 
/*Affichier les autres*/
for(indice=0;indice<K;indice++)
      {
       while(UneCombinaison[indice]>indice+1)
              {
               UneCombinaison[indice]--;
               Affichier_Combinaison(UneCombinaison,K);
               NbrCombinaisaon++;/*mise à jours du nombre de combinaison*/
              }
 
      }
 
printf("nombre de combinaisons %d ",NbrCombinaisaon);
getch();
}

**Trap D** · 24/10/2006, 16h42

Code :

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

void main()

Qu'est-ce que c'est que ce prototype ??

Code :

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

int main(void)

**zhao** · 25/10/2006, 01h25

Bonjour a tous .
je viens de lancer ce programme mais le resultat ne correspond pas a ce que je veux ,par exemple si je le lance pour trouver 6 chiffre parmi 10 il en trouve 18 alors qu'en realité il y en a 210 ,avec 6 parmi 8 il en trouve 6 au lieu de 28 etc... donc desolé c'est pas bon , dommage car 3 boucles quelque soit N et K aurais ete genial ;-)
cordialement

**Trap D** · 25/10/2006, 14h47

Pour faire ce programme, on utilise un tableau combinaison de k nombres, si k est le nombre d'éléments de la combinaison, on suppose <ue n est le nombre maximum.
L'algo donnera ça :

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
 
// initialisation
pour j de 1 à k faire
  combinaison|j] <- j
fin pour
 
possible <- vrai
tant que possible = vrai faire
  afficher le tableau combinaison 
  j <- k
  combinaison[j] <- combinaison[j] + 1
  // on regarde si on a atteint le maximum possible pour la case
  // si c'est le cas on passe à la case précédente
  tant que possible = vrai et combinaison[j] = n - (k-j) + 1 faire
    j <- j - 1
    si j = 0 alors
      possible <- faux
    sinon
      combinaison[j] <- combinaison[j] + 1
    fin si
  fin tant que
 
  // a-t-on épuisé toutes les combinaisons ?
  si possible = vrai alors
    // si on peut toujours afficher une combinaison
    // on initialise la fin du tableau combinaison 
    j <- j + 1
    tant que j <= n faire
      combinaison[j] <- combinaison[j - 1] + 1
      j <- j + 1
    fin tant que
  fin si
fin tant que

**zhao** · 25/10/2006, 15h14

Envoyé par Trap D

Pour faire ce programme, on utilise un tableau combinaison de k nombres, si k est le nombre d'éléments de la combinaison, on suppose <ue n est le nombre maximum.
L'algo donnera ça :

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
 
// initialisation
pour j de 1 à k faire
  combinaison|j] <- j
fin pour
 
possible <- vrai
tant que possible = vrai faire
  afficher le tableau combinaison 
  j <- k
  combinaison[j] <- combinaison[j] + 1
  // on regarde si on a atteint le maximum possible pour la case
  // si c'est le cas on passe à la case précédente
  tant que possible = vrai et combinaison[j] = n - (k-j) + 1 faire
    j <- j - 1
    si j = 0 alors
      possible <- faux
    sinon
      combinaison[j] <- combinaison[j] + 1
    fin si
  fin tant que
 
  // a-t-on épuisé toutes les combinaisons ?
  si possible = vrai alors
    // si on peut toujours afficher une combinaison
    // on initialise la fin du tableau combinaison 
    j <- j + 1
    tant que j <= n faire
      combinaison[j] <- combinaison[j - 1] + 1
      j <- j + 1
    fin tant que
  fin si
fin tant que

Bonjour
en language C ca donne quoi exactement car j'ai eu confirmation que mon probleme peut se resoudre avec 2 for ,grrrrrrrrrr que c'est enervant de ne pas savoir ;-) hors si je ne me trompe pas toi tu n'as qu'une seule boucle ( car je suppose que " pour et fin pour " sont une boucle et tant que fin tant que des while ?) bref tu vois pourquoi je demande si tu peut me coder ca en C si j'abuse pas trop bien sur ;-)
cordialement

**Trap D** · 25/10/2006, 15h43

Ben si, tu abuses un peu : tu montres ce que tu tires en C de l'algo, tu expliques où tu m***des et là je t'aiderai

N'oublie pas qu'en C les indices commencent à zéro.

PS : la boucle for est un piège, utilise des tant que, c'est plus simple à manipuler.

**zhao** · 26/10/2006, 02h01

Bonjour :-)

bon j'ai fait le code inutile de te dire que le resultat n'est pas vraiment ce que j'attendais j'ai du faire pas mal d'erreur ;-)

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
35
36
37
#include <stdio.h>
#include <dos.h>
#include <stdlib.h>
#define	FALSE	(0)
#define	TRUE	(!FALSE)
main()
{
      int j,k,n=6,combinaison[50];
      int possible=TRUE;
      printf("combien de numeros ? \n");
      scanf("%d",&k);
      for(j=1;j==k;j++)
      combinaison[j]=j;
      while(possible)
      {
        printf(" % d ",combinaison[j]);
        j=k;
        combinaison[j]=combinaison[j]+1;
        while(possible && combinaison[j]==n - (k-j)+1)
        {
                       j=(j-1);
                       if ( j==0)
                       possible=FALSE;
                       else
                       combinaison[j]=combinaison[j]+1;
         } 
         if(possible==TRUE)
          {
         j=j+1;
            while(j<=n)
              {
                       combinaison[j]=combinaison[j-1]+1;
                       j=j+1;
              }
           }
        }
        }

cordialement

Calcul de toutes les combinaisons de N parmi K

C

Discussions similaires

Partager

Partager