Tableau : combinaisons d'elements

Version imprimable

salut tout le monde
j essaye de mettre en place un algoritme qui pourrait me donner toutes les combinaisons possibles de ses elements (doublons de lettre egalement. ex : AA,BB)
je disposed'un algo recursif qui me permet de permuter les valeurs mais le probleme c'est que je voudrai integrer le fait qu'il stock chaque ensemble de combinaison creer dans un tableau et je ne vois pas comment m'y prendre et qu'il puisse gerer le fait qu'il puiise y avoir des doublons :? (etant pas tres doué avec le recursif)
pour le moment le programme se contente d'afficher les lettres une part une

voici l'algo en question :
Code:

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 #include <stdio.h> #include <stdlib.h> void permutation( char* e, int nb, int rang) ; int main( int argc, char** argv ) { int nb ; /* Le nombre d'entier à permuter */ char entree[3]={'A','B','C'} ; /* Le tableau qui contiendra les nombres */ int i; printf( "Nb d'entier : " ) ; fflush(stdin) ; fflush( stdout ) ; scanf( "%d", &nb ) ; permutation( entree, nb, 0) ; return 0 ; } void permutation(char* e, int nb, int rang) { int i, j ; if ( rang == nb-1 ) /* Le zone à permutter ne contient qu'un élément */ { char* sep = "" ; for( i=0; i<nb; i++ ) { printf( "%s%c", sep, e[i]) ; sep = ", " ; } printf( "\n" ) ; } else for( i=rang; i<nb; i++ ) { int prem ; permutation( e, nb, rang+1) ; /* on fait tourner les éléments de la zone à permutter */ prem = e[rang] ; for( j=rang+1; j<nb; j++ ) e[j-1] = e[j] ; e[nb-1] = prem ; } }
ps : en simple test j'ai essayer de numéroter chaque ensemble de combinaison et je me retrouve avec des ensembles ayant le meme numero

pouvez vous m'eclairer a ce sujet !

Voila le code de départ il ne manque plus qu'à rajouter quelques petit truc pour effectuer les doublons;):

Code:

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
#include <stdio.h>
#include <stdlib.h>
 
void purger(void);
void permutation(int *e, int nb, int rang);
 
int main(void)
{
    int nb, *entree, i;   /* nb est le nombre d'entier à permuter */
                          /* entree est le tableau qui contiendra les nombres */
 
    printf("Nombre d'entier : ");
    fflush(stdout);
    scanf("%d", &nb), purger();
    entree = malloc(nb *sizeof(int));
    if (!entree)
    {
        perror("malloc:");
        return 1;
    }
    for(i=0;i<nb;i++)
    {
        printf("Entier %d : ", i+1);
        fflush(stdout);
        scanf("%d", entree+i), purger();
    }
    permutation(entree, nb, 0);
    free(entree);
    return 0;
}
 
void permutation(int *e, int nb, int rang)
{
    int i, j, prem;
    char *sep = "";
 
    if (rang == nb-1) /* Le zone à permutter ne contient qu'un élément */
    {
        for(i=0;i<nb;i++)
        {
            printf("%s%d", sep, e[i]);
            sep = ", ";
        }
        printf("\n");
    }
    else
    {
        for(i=rang;i<nb;i++)
        {
            permutation(e, nb, rang+1);
            prem = e[rang];                              /* on fait tourner les éléments de la zone à permutter */
            for(j=rang+1;j<nb;j++)
            {
                 e[j-1] = e[j] ;
            }
            e[nb-1] = prem ;
        }
    }
}
 
 
void purger(void)
{
  int c;
  while ((c = getchar()) != '\n' && c != EOF)
  { ; }
}

EDIT: petite correction du code pour rentré dans la norme^^

17/03/2008, 18h32
snipes

je n'ai pas trop compris ce que tu as changé dans le code :aie: en fait mi s a part la fonction purger j'ai pas vu de changement 8O

sinon je me trouve confronter a un nouveau probleme: en fait mon tableau de caractere 'entree' est constitué des lettres de l alphabet en Majuscule et en Minuscule donc la valeur de ma variable "nb" sera de 52^52 !! si je veux conserver toutes mes combinaisons ca sera tout simplement pas faisaible ?
17/03/2008, 19h10
snipes

arf je viens de me rendre compte apres un test que l'algo en question ne correspond pas a ce que je veux car pour une longueur donnée il va faire la permutation en prenant que cette longueur dans le tableau contenant les valeurs

exemple

char test[3] = {'A','B','C'};

si jdonne la longueur 2 j aurais droit a une permutation que de A et B or ce que je souhaite avoir c'est une permutation avec tout les elements possible mais de longueur 2 a savoir

AA,AB,AC
BA BB BC
CA CB CC

ps : ceci-dit merci pour ta participation snake264 !!!

voici ce que j'ai reussi a faire pour n=3 ( je pense que je vais finalement m'arreter a n=5 et laisser n=x pour une prochaine fois)
Code:

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<string.h> #define NB_ELT 65 int main(void) { int i,j,k; int total = 0; char valeur[3]; unsigned char ALL[NB_ELT] = { 'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','1','2','3','4','5','6','7','8','9','0' }; for(i=0;i<3;i++) valeur[i] = '\0'; for (i=0; i<NB_ELT; i++) { for (j=i; j<NB_ELT-1; j++) { for (k=j; k<NB_ELT-2; k++) { valeur[0] = ALL[i]; valeur[1] = ALL[j]; valeur[2] = ALL[k]; valeur[3] = '\0'; printf("%s\n",valeur); if(strcmp(valeur,"dA0") == 0) { printf("Valeur trouvee !\n"); return 0; } total ++; // stocke le nombre de combinaisons totales } } } }
cependant j'ai un petit probleme ! je ne peux generer que des combinaisons qui suivent l'ordre dans lequel apparaisse les elements du tableau (ex : BAC marche pas vu que B apparait avec A , ABC = ok)
je ne vois pas non plus comment adapter ceci o fait que l'on puisse choisir la taille du mot (compri entre 0 et 5)
:roll: