J'ai oublié: dans le cas de l'énoncé ci-dessus on devrait donc obtenir avec n=10 et Z = {A,T,G,C}
4^10=1048576 possibilités, allant de AAAAAAAAAA à TTTTTTTTTT. Je pense que pour n>20 la combinatoire devient énorme et le programme quel qu'il soit prendrait énormément de temps de calcul.

[code]

#include <vector>
#include <iostream>
#include <cassert>


void f(
unsigned prof, // la profondeur courante (nombre de chiffre choisis)
const unsigned & prof_max, // la profondeur max (nombre de chiffre à choisir)
std::vector<short> perm, // la permutation courante
std::vector<bool> marked, // les nombres utilisés
unsigned & compteur // le nombre de permutations rencontrées
){
if (prof < prof_max){
for(unsigned i=1;i<=4;++i){
if (marked[i]) continue;
std::vector<short> perm_suivant = perm;
perm_suivant.push_back(i);
std::vector<bool> marked_suivant = marked;
marked_suivant[i] = true;
f(prof+1,prof_max,perm_suivant,marked_suivant,compteur);
}
}else{ // le nombre a la taille voulue
for(unsigned i=0;i<perm.size();++i) std::cout << perm[i];
std::cout << std::endl;
++compteur;
}
}

void perm(const unsigned & prof_max){
assert(prof_max<=4);
std::vector<short> perm0;
std::vector<bool> marked0(4,false);
unsigned compteur = 0; // partagé par tous les appels recursifs
f(0,prof_max,perm0,marked0,compteur);
std::cout << "compteur = " << compteur << std::endl;
}

int main(){
perm(4);
return 0;
}
[code]

je comprend pas pourquoi ce code me renvoit une dernière ligne 4444 et pas les lignes 1111,2222,3333 !

Pour les personnes qui tomberaient sur ce fil, je précise que le programme évoqué par mslider est ici :
http://www.commentcamarche.net/forum/affich 3075042 comptabiliser des permutations en c?#1

Tu peux coder en binaire mais ça ne change pas grand chose au problème, à la limite la conversion binaires ou entiers vers lettres peut se faire simplement au niveau de la fonction d'affichage. En soit vu que la structure n'es jamais stockée en mémoire et qu'il n'y a que n caractères avec n très petit, autant travailler avec des entiers et reprendre comme tu l'as fait le programme que j'ai écrit.

Pour répondre à ta question, le vecteur marked vérifie dans le programme initial qu'un nombre n'a pas été déjà utilisé à ce niveau :

if (marked[i]) continue;

#include <vector>
#include <iostream>

#define TAILLE_ALPHABET 4

char int_to_char(short x){
    if      (x == 0) return 'A';
    else if (x == 1) return 'T';
    else if (x == 2) return 'G';
    else if (x == 3) return 'C';
    return '?';
}

void f(
    unsigned prof,              // la profondeur courante (nombre de chiffre choisis)
    const unsigned & prof_max,  // la profondeur max (nombre de chiffre à choisir)
    std::vector<short> perm,    // la permutation courante
//  std::vector<bool> marked,   // les nombres utilisés
    unsigned & compteur         // le nombre de permutations rencontrées
){
    if (prof < prof_max){
        for(unsigned i=0;i<TAILLE_ALPHABET;++i){
//          if (marked[i]) continue;
            std::vector<short> perm_suivant = perm;
            perm_suivant.push_back(i);
//          std::vector<bool> marked_suivant = marked;
//          marked_suivant[i] = true;
//          f(prof+1,prof_max,perm_suivant,marked_suivant,compteur);
            f(prof+1,prof_max,perm_suivant,compteur);
        }
    }else{ // le nombre a la taille voulue
        for(unsigned i=0;i<perm.size();++i) std::cout << int_to_char(perm[i]);
        std::cout << std::endl;
        ++compteur;
    }
}

void perm(const unsigned & prof_max){
    std::vector<short> perm0;
//  std::vector<bool> marked0(TAILLE_ALPHABET,false);
    unsigned compteur = 0; // partagé par tous les appels recursifs
//  f(0,prof_max,perm0,marked0,compteur);
    f(0,prof_max,perm0,compteur);
    std::cout << "compteur = " << compteur << std::endl;
}

int main(){
    perm(2);
    return 0;
}

AA
AT
AG
AC
TA
TT
TG
TC
GA
GT
GG
GC
CA
CT
CG
CC
compteur = 16

Je vais peut être dire une connerie, mais il ne serai pas plus simple et plus rapide de faire des boucles ?
Bonne chance pour ton programme de bio ;) Salutation !  avant je croyais, maintenant je suis fixé.Jésu­s Christ
Char Snipeur

J'avais pensé à faire des boucles au départ avec ce programme qui d'ailleurs n'est pas complet:

void generateNeighbours(int motifwidth, string m, int nn)
{
   int i, j, k, l; string strmotif;
   vector < int > motif;
   vector < int > neigh;
   vector < vector <int> > partial;
  
   for(i = 0; i < m.size(); i++)
   {
       string base = m.substr(i,1);
       motif.push_back(checkBase(base));
   }
  
   original = m;
   nemotifs.push_back(m);
   neighbours.push_back(motif);
  
   neigh = motif;
   if(nn == 1 || nn == 2)
   {
       for(k = motifwidth-1; k >= 0; k--)
       {
           for(j = 0; j <= 3; j++)
           {
               neigh[k] = j;
               if(neigh != motif)
               {
                   neighbours.push_back(neigh);
                   partial.push_back(neigh);
                   for(int g = 0; g < neigh.size(); g++)
                   {
                       strmotif += nucleotideUnhash(neigh[g]);
                   }
                   nemotifs.push_back(strmotif);
                   strmotif.clear();
               }
           }
           neigh = motif;
       }
   }
  
   if(nn == 2)
   {   
       for(i = 0; i < partial.size(); i++)
       {
           neigh = partial[i];
           for(k = motifwidth-1; k >= 0; k--)
           {
               for(j = 0; j <= 3; j++)
               {
                   neigh[k] = j;
                   if(neigh != partial[i])
                   {
                       neighbours.push_back(neigh);
                       for(int g = 0; g < neigh.size(); g++)
                       {
                           strmotif += nucleotideUnhash(neigh[g]);
                       }
                       nemotifs.push_back(strmotif);
                       strmotif.clear();
                   }
               }
           neigh = partial[i];
           }
       }
   }
   checkMotifs();
  
}

De rien :-)

Pour les boucles c'est possible mais pas de manière simple. Là c'est un parcours d'arbre (algo exponentiel) donc c'est plus naturel de l'écrire en récursif. Les boucles sont plus indiquées pour des algorithmes polynomiaux (parcours d'un tableau ou d'une matrice par exemple).

Bonne continuation