Discussion :

[Darksnakes]

Bonjour à tous

voilà je suis sur un projet actuellement et j'aurais voulu savoir si il existe en c (voir en c++) une fonction qui donne la liste de toutes les permutations de n parmis p.

Si cela n'existe pas pourriez vous m'aider pour un algorithme.

je cherche un algo qui prend en paramètre 2 chiffres (x et y tel que x<=y) et un pointeur sur un tableau d'entier(à double entrée).
L'algorithme calcul le nombre de combinaisons possible (x parmis y, j'ai déjà créé cette fonction (x parmis y=y!/((y-x)!*x!)=k), ce qui donnent la taille du tableau (y*k) et créé le tableau . Le soucis c'est que je ne trouve pas d'algorithme pour remplir le tableau avec des 1 et 0.


Exemple de solutions : Combinaison(p,3,5)
3 parmis 5 = 10

tableau p(taille=5*10):
0)11100
1)11010
2)11001
3)10110
4)10101
5)10011
6)01110
7)01101
8)01011
9)00111

Si quelqu'un à un début de piste, j'en serait reconnaissant

PS:
existe t'il dejà les fonctions Factoriel et Combinaison en c? ou dois-je gardais celles que j'ai créées?

[Zavonen]

Thème récurrent il y a beaucoup de ressources sur ce forum, en particulier:
http://www.developpez.net/forums/d42...-combinaisons/
Voir aussi mon cours BASES-->ensembles-->parties

[Darksnakes]

A première vu c'est ce qu'il me faut
Je vais essayer ça dessuite et vous tenir au courant merci beaucoup

[Darksnakes]

j'ai réussi a adapter ta solution, merci bcp

par contre je suis tomber sur une autre solution :

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
 
void afficher( int *p, int n) {
  int i;
  for (i = 0; i < n; i++) printf("%d ", p[i]);
  printf("\n");
}
 
void combi2(int cmb[], int n, int p , int i, int k) {
    if (k == p) afficher(cmb,p);
    else if (i < n) {
        combi2(cmb,n,p,i+1,k);
        cmb[k] = i;
        combi2(cmb,n,p,i+1,k+1);
    }
}
 
 
 
int main() {
  int combi[3];
  combi2(combi,5,3,0,0);
  return 0;
}

j'aurais voulu comprendre le fonctionnement, ou plutot la logique de l'algo.
merci d'avance


Yann

[Zavonen]

J'ai regardé ça vite fait. A priori je ne comprends pas la logique non plus. Ce n'est pas documenté du tout. Pour comprendre il faudrait faire une trace, bref cela prend du temps...

[pseudocode]

C'est le meme principe que celui que j'ai posté.

La différence etant que pour une profondeur donnée je fais le parcours des éléments possibles avec une boucle for():

Code java :

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

1
2
3
4
5
 
for(int i=start;i<n;i++) {  // <-- parcours des éléments possibles
    liste[index]=i;
    partition(index+1);  // <-- passage a la profondeur suivante
}

alors que dans le meme cas il font le parcours des éléments possibles par récursion:

Code C :

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

1
2
3
4
5
6
 
if (i < n) {
    combi2(cmb,n,p,i+1,k);  // <-- parcours des éléments possibles
    cmb[k] = i;
    combi2(cmb,n,p,i+1,k+1);  // <-- passage a la profondeur suivante
}

[Darksnakes]

ok merci beaucoup

bonne soirée!!