Discussion :

[Hind4Dev]

j'ai besoin de générer depuis un nombre n et k toutes les combinaisons possibles

exemple:
n = 3 k = 2

Code :

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

1
2
3
4
5
6
7
 
0 0 0
0 1 0
0 1 1
1 1 1
1 2 0
...

n est le nombre de variables et k est le domaine des valeurs possibles
je ne sais comment procéder en utilisant juste un tableau statique

[picodev]

Bonjour,

tout est expliqué dans le fascicule 3A du volume 4 du TAOCP de Knuth. De plus tu as une implémentation disponible ici sur dvp → Générateur de combinaisons.

[Hind4Dev]

merci

[Hind4Dev]

j'ai trop essayé mais ça fonctionne toujours pas mes algorithmes

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
 
void genere(int n, int k, int nbr_comb) {
 
 
    int p[nbr_comb][n];
    int q = -1;
    int res;
    int r = 0;
 
 
    int tab[n];
    int i, j;
    for ( i = 0; i < nbr_comb; i++) {
        for ( j = 0; j < n; j++) {
            while (q != 0) {
                q = n / (k + 1);
                r = n % (k + 1);
                p[i][j] = r;
                p[i][j+1] = q;
                n = q;
            }
 
        }
        printf("%d \n",p[i][j]);
    }
}
int main() {
    int n = 3;
    int k = 2;
    int nbr_comb = pow((k + 1), n);
 
 
    genere( n,  k,  nbr_comb);
 
 
    return (EXIT_SUCCESS);
}

[ternel]

A la main, cherche la liste de toutes les combinaisons de 3 chiffres valant 0, 1, 2 ou 3.

Une fois fait, demande toi:

• comment tu as trouvé chaque élément de la liste?
• comment tu sais que la liste est complete?
• comment sais-tu que la liste ne contient pas d'intrus?

Puisque tu as procédé systématiquement, il suffit de formaliser un peu ta méthode.

[Hind4Dev]

j'ai réessayé avec ce code

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
 
void generate(int n, int k) {
   int q = -1;
   char res = '|';
   int r; 
   int j;
   for (j = 1; j <= n; j++) {
       q = j / (k + 1);
       r = j % (k + 1);
       printf("%d %c", r, res);
    }
}
int main() {
   int n = 3;
   int k = 2;
   int i, nbr_comb; 
   nbr_comb = pow((k + 1), n); 
 
 
   for (i = 0; i < nbr_comb; i++) {
       generate(n, i);
       printf("\n");
   }
   return (EXIT_SUCCESS);
}

voilà ce que ça donne

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
0 |0 |0 |
1 |0 |1 |
1 |2 |0 |
1 |2 |3 |
1 |2 |3 |
1 |2 |3 |
1 |2 |3 |
1 |2 |3 |
1 |2 |3 |
1 |2 |3 |
1 |2 |3 |
1 |2 |3 |

il commence à générer puis il se fixe, je ne comprends pas pourquoi

[ternel]

Je ne comprends pas du tout ton code, qui génère plein de choses.
par combinaisons, on entend bien les N-uplets de nombres générables à partir des nombres compris entre 0 (inclus) et K (exclus).
Ces combinaisons sont considérées identiques si elles ne diffèrent que par l'ordre des valeurs (sinon, on parlerait d'arrangements.).

C'est à dire pour N = 2 et K = 3: {0, 0} {0, 1} {0, 2} {1, 1} {1, 2} {2, 2}

Sans ordinateur comment génères-tu cette liste?
Je t'aiderai à traduire ca en code, mais je ne te donnerais pas la réponse à la méthode.

Programmer, ce n'est pas écrire du code, c'est expliquer une méthode à un ordinateur. Et tu ne peux pas l'expliquer tant qu'elle n'est pas claire dans ta tête.

[Hind4Dev]

je vais t'expliquer comment je vois les choses en main comme tu dis.
je les vois comme une hiérarchie en arbre, j'ai dans la racine toutes les valeurs de k (mon vecteur N)
par exemple pour n= 3 k =2: racine = 0 1 2
de chaque élément je commence à générer le même vecteur j'aurai alors pour 0 (0 1 2) pour 1 et 2 même chose ainsi de suite avec un niveau de N fois, comme ça j'aurai toutes les combinaisons possibles

est ce exact ?

[ternel]

Peut-être, mais je n'ai pas compris ton explication.

Pour générer tous les arrangements, je procède ainsi.

Soient N entiers, les éléments d'un arrangement (numéroté de 1 à N)
Ils valent tous 0 initialement.

afficher les N entiers.
//chercher l'arrangement suivant.
si le premier entier ne vaut pas K, l'augmenter sinon
   si le suivant ne vaut pas K, l'augmenter sinon
      ...etc jusqu'à l'entier N-1 compris
         ... si l'entier N ne vaut pas K, l'augmenter sinon
            c'est terminé
si ce n'est pas terminé, recommencer à partir de l'affichage.

Il me faut donc une fonction pour passer à l'arrangement suivant, une seconde pour l'afficher, et main qui appelle les deux.

Maintenant, tu ne cherches que les combinaisons. Elles ont pour propriété d'être insensible à l'ordre de leurs éléments.
Il suffit donc de ne considérer que celles dont les éléments sont en ordre croissant.
C'est uniquement la fonction de "suivante" qui change.

[Hind4Dev]

merci beaucoup, c'est ce que j'ai fait, ça fonctionne bien maintenant

[ternel]

Et du coup, à quoi ressemble ton code?

[Hind4Dev]

à ça:

Code :

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

1
2
3
4
5
6
7
8
9
 
for (row = 0; row < nbr_comb; row++) {
        for (col = n - 1; col >= 0; col--) {            
            rdiv = pow(k + 1, col); 
            cell = (row / rdiv) % (k + 1);
            pigeon[col] = cell;
        }
    }
}

[ternel]

Tu pourrais améliorer ton code, il n'est pas nécessaire de calculer la division pour obtenir le reste.
Ainsi, (row / (pow(k + 1, col))) % (k + 1) est toujours égal à row % (k + 1).
Tu gagneras en performance (même si ce n'est pas forcément nécessaire) et surtout en lisibilité.
Tout en supprimant une variable, ce qui n'est jamais vraiment perdu.