liste des n-uplets d'un ensemble a nb elementRésolu

Question

voila mon probleme:
soit E un ensemble et card(E)=nb;
mon programme doit calculer la liste de toutes les combinaisons possibles a n elements
j'avais pensé faire ca avec un rand() donc g redefini RAND_MAX mais ca ne passe pas (le rand me sort des valeurs dans ce genre :s 41184676334265001916915724)
donc j'aimerais savoir si quelqu'un connait un myen plus systematique (et plus fiable) de calculer les n-uplets d'un ensemble
NB: j'ai chercher sur google, mais vu mon niveau en math la plupart des sites mon embrouillé

Guillemouze · Accepted Answer

c peut etre normal. tu a 266 possibilites, soit 308.915.776
si tu multiplie par le nombre de caracteres pour chaque possiblilites (6 lettres + 1 retour) = 2.162.410.432 caracteres
si ton caracter fait 1 octet, ca fait 2.162.410.432 octets, soit 2.111.728 Ko,  2.062 Mo, 2Go, 
donc c bizar ton fichier est un petit peu petit, si jme trompe pas !!!

A part ca , il vaut mieux que tu remplace
chaine[X] = alphab[Y] 
par 
chaine[X] = (char) (67 + Y)
et que tu fasse cette affectation juste apres la boucle
for (Y=0; Y<26;Y++)
pour minimiser le nombre doperations

alussk · Answer

oops j'aurais ptet du parcourir le forum avant...
enfin bref maintenant g un autre probleme
j'ai coder cette fonction:
void six_uplet_alphB(char *chaine){
     int i,c,j,k,l,m,n;
     char alphab[26]={'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'};
      FILE *Fchaine;
      if((Fchaine=fopen("C:\Documents and Settings\Administrateur\Bureau\ssk,log.txt","w+"))==NULL){
        printf("ERREUR D'OUVERTURE DU FICHIER DE SAUVEGARDE");
        }
      for(i=0;i<26;i++){
       for(j=i+1;j<26;j++){
        for(k=j+1;k<26;k++){
         for(l=k+1;l<26;l++){
          for(m=l+1;m<26;m++){
           for(n=m+1;n<26;n++){
              chaine[0]=alphab[i];
              chaine[1]=alphab[j];
              chaine[2]=alphab[k];
              chaine[3]=alphab[l];
              chaine[4]=alphab[m];
              chaine[5]=alphab[n];
              for(c=0;c<6;c++);
                fprintf(Fchaine,"%c",chaine[c]);
              fprintf(Fchaine,"
");
           }
          }
         }
        }
       }
      }   
}
mais rien ne s'affiche dans le fichier... je vois pas trop pourquoi, donc plz help

Guillemouze · Answer

heu la tu genere pas tous les combinaisons, mais seulement celles dont les lettres qui precedent sont inferieurs a celles qui suivent. si tu les veu toutes, tu peu faire:

void six_uplet_alphB(char *chaine){
     int i,c,j,k,l,m,n;
      FILE *Fchaine;
      Fchaine = fopen("C:\Documents and Settings\Administrateur\Bureau\ssk,log.txt","w+");
      if(Fchaine == NULL){
        printf("ERREUR D'OUVERTURE DU FICHIER DE SAUVEGARDE");
        return;
       }
       for(i=0;i<26;i++){
         chaine[0]=(char)(i+67); //i+67 doit etre le code ASCII de ta lettre            
         for(j=0;j<26;j++){
           chaine[1]=(char)(j+67); // il me semble que 67 est le code de "a"

           for(k=0;k<26;k++){
             chaine[2]=(char)(k+67);//si c pas le cas, remplace 67 par le bon code

             for(l=0;l<26;l++){
               chaine[3]=(char)(l+67);

               for(m=0;m<26;m++){
                 chaine[4]=(char)(m+67);

                 for(n=0;n<26;n++){
                    chaine[5]=(char)(n+67);
                   fprintf(Fchaine,"%s
",chaine);
                }
            }
         }
      }
    }
  }  
}

Guillemouze · Answer

heuuuu oublie pas de declarer 

char chaine[5];

aussi

Guillemouze · Answer

char chaine[6] 
pardon

alussk · Answer

Je vois le principe,
j'avais déja corrigé (et oublié que j'avais posté xD)
et ca donnait ca:
for(i=0;i<26;i++){
          for(j=0;j<26;j++){
           for(k=0;k<26;k++){
            for(l=0;l<26;l++){
             for(m=0;m<26;m++){
              for(n=0;n<26;n++){
               chaine[0]=alphab[i];
               chaine[1]=alphab[j];
               chaine[2]=alphab[k];
               chaine[3]=alphab[l];
               chaine[4]=alphab[m];
               chaine[5]=alphab[n];
               chaine[6]='\0';
              }
             }
            }
           }
          }   
         }

franchement je serais tenté de dire que ca revient au meme, mais vu que j'ai pa pu tester.. ca ma donner un .txt de 600Mo(bizarre?) qui m'a planté le notepad...
donc vala si ce n'est pas la meme, ou tout simplement si c'est moins bien dis le moi

Guillemouze · Answer

ce que je te conseille c de faire un arbre
dans le genre

typedef struct {
    char lettre;
    Noeud *fils[26];
} Noeud;

Noeud* racine;

racine = rempliArbre(' ', 6);

Noeud* rempliArbre(char val, int prof);
    if (prof == 0) return NULL;
    Noeud* tmp = malloc(sizeof(Noeud));
    tmp->lettre = val;
    for (i=0;i<26;i++) {
        tmp->fils[i] = rempliArbre((char)(67+i), prof-1);
    }
    return tmp;
}

et pour lister, t'a plus qu'a parcourir l'arbre

alussk · Answer

ouaou, je connais pas encore les structures mais bon on dira que c'est le moment de s'y mettre, par contre je te demanderai juste une derniere info, avec ta methode on le parcous comment l'arbre?

Guillemouze · Answer

bah si tu veu afficher toutes les possibilites a l'ecran, tu fai

char buffer[7];
buffer[6] = 0;
void afficher(Noeud* noeud, char *buffer, int prof) {
    if (prof == 0) printf("%s
", buffer);
    else {
        buffer[5-prof] = noeud->lettre;
        for (i=0;i<26;i++) afficher(noeud->fils[i], buffer, prof-1);
    }
}

a quelques choses pret ca doit etre un druc dans ce genre.

mais l'utilisation d'un arbre depend aussi des traitement que tu veu en faire apres. peut etre que c'est pas utile!!!

Liste des n-uplets d'un ensemble a nb element

9 réponses

Votre réponse