Comment capturer une chaîne en variable dans une fonction récursive?

Question

J'ai essayé d'imprimer toute la combinaison possible de membres de plusieurs vecteurs. Pourquoi la fonction ci-dessous ne retourne pas la chaîne comme je m'y attendais?

#include <iostream> 
#include <vector> 
#include <fstream> 
#include <sstream> 
using namespace std; 

string EnumAll(const vector<vector<string> > &allVecs, size_t vecIndex, string 
     strSoFar) 
{ 
    string ResultString; 
    if (vecIndex >= allVecs.size()) 
    { 
     //cout << strSoFar << endl; 
     ResultString = strSoFar; 
     //return ResultString; 
    } 
    for (size_t i=0; i<allVecs[vecIndex].size(); i++) { 
     strSoFar=EnumAll(allVecs, vecIndex+1, strSoFar+allVecs[vecIndex][i]); 
    } 
    ResultString = strSoFar; // Updated but still doesn't return the string. 
    return ResultString; 

} 


int main (int arg_count, char *arg_vec[]) { 

    vector <string> Vec1; 
      Vec1.push_back("T"); 
      Vec1.push_back("C"); 
      Vec1.push_back("A"); 

    vector <string> Vec2; 
      Vec2.push_back("C"); 
      Vec2.push_back("G"); 
      Vec2.push_back("A"); 

    vector <string> Vec3; 
      Vec3.push_back("C"); 
      Vec3.push_back("G"); 
      Vec3.push_back("T"); 


    vector <vector<string> > allVecs; 

    allVecs.push_back(Vec1); 
    allVecs.push_back(Vec2); 
    allVecs.push_back(Vec3); 




    string OutputString = EnumAll(allVecs,0,""); 

    // print the string or process it with other function. 
    cout << OutputString << endl; // This prints nothing why? 

    return 0; 
} 

Le résultat attendu est:

TCC 
TCG 
TCT 
TGC 
TGG 
TGT 
TAC 
TAG 
TAT 
CCC 
CCG 
CCT 
CGC 
CGG 
CGT 
CAC 
CAG 
CAT 
ACC 
ACG 
ACT 
AGC 
AGG 
AGT 
AAC 
AAG 
AAT 

Answer 1

Voici une solution de rechange. Cela ne vous attendez pas à passer quoi que ce soit, mais les vecteurs initiaux:

int resultSize(vector< vector<string> > vector){ 
int x=1; 
for(int i=0;i<vector.size(); i++) 
    x *= vector[i].size(); 
return x; 
} 

vector<string> enumAll(const vector< vector<string> > allVecs) 
{ 
//__ASSERT(allVecs.size() > 0); 
vector<string> result; 
if(allVecs.size() == 1){ 
    for(int i=0 ; i< allVecs[0].size(); i++){ 
    result.push_back(allVecs[0][i]); 
    } 
    return result; 
} 
for(int i=0; i<allVecs[0].size(); i++){ 
    for(int j=0; j<resultSize(vector< vector<string> >(allVecs.begin()+1, allVecs.end())); j++){ 
    result.push_back(allVecs[0][i] + enumAll(vector< vector<string> >(allVecs.begin()+1, allVecs.end()))[j]);//enumAll on each tempVector is called multiple times. Can be optimzed. 
    } 
} 
} 

avantage de cette méthode: Ceci est très lisible en termes de récursivité. Il a une étape de base de récursion facilement identifiable et aussi la récursivité elle-même. Cela fonctionne comme suit: Chaque itération de la récursion énumère toutes les chaînes possibles de n-1 vecteurs et l'étape courante les énumère simplement. Inconvénients de cette méthode: 1.La fonction enumAll() est appelée plusieurs fois pour renvoyer le même résultat. 2. Utilisation lourde sur la pile puisque ce n'est pas la récursivité de la queue.

Nous pouvons corriger (1.) en procédant comme suit, mais à moins d'éliminer la récursion de queue, nous ne pouvons pas nous débarrasser de (2.).

vector<string> enumAll(const vector< vector<string> > allVecs) 
{ 
//__ASSERT(allVecs.size() > 0); 
vector<string> result; 
if(allVecs.size() == 1){ 
    for(int i=0 ; i< allVecs[0].size(); i++){ 
    result.push_back(allVecs[0][i]); 
    } 
    return result; 
} 
const vector< vector<string> > tempVector(allVecs.begin()+1, allVecs.end()); 
vector<string> tempResult = enumAll(tempVector);// recurse 
int size = resultSize(tempVector); 
cout << size << " " << tempResult.size() << endl; 
for(int i=0; i<allVecs[0].size(); i++){ 
    for(int j=0; j<size; j++){ 
    result.push_back(allVecs[0][i] + tempResult[j]); 
    } 
} 
} 

Answer 2

Votre fonction ne retourne rien parce que votre dernier appel ne retourne rien car il n'y a pas return et la fin de votre fonction.

Edit: Une chose que vous pouvez faire, est d'insérer votre ResultString à un vecteur global à chaque fois avant le return. Et à la fin, tous vos résultats seront disponibles dans ce vecteur.

Answer 3

Vous appelez EnumAll récursivement, mais vous ignorez la chaîne qu'il renvoie. Vous devez décider comment vous allez agréger ces chaînes - ou ce que vous allez en faire.

Answer 4

Votre deuxième retour devrait également accumuler le strSoFar d'une manière ou d'une autre. Quelque chose comme:

for (size_t i=0; i<allVecs[vecIndex].size(); i++) 
{ 
    strSoFar = EnumAll(allVecs, vecIndex+1, strSoFar+allVecs[vecIndex][i]); 
} 
ResultString = strSoFar; 
return ResultString; 

Answer 5

Le code que vous avez fourni se bloque. Dans la ligne suivante, notez que vous dépasserez les limites de vecIndex. Il n'y a pas de vérification dans la boucle. En outre, dans la condition if ci-dessus, vous ne devez pas non plus réinitialiser le vecIndex. Donc, vous aurez une violation d'accès.

strSoFar = EnumAll(allVecs, vecIndex+1, strSoFar+allVecs[vecIndex][i]); 

Pour résoudre ce problème, que ce soit le repos vecIndex dans le cas() ou utiliser les éléments suivants pour la déclaration:

for (size_t i=0; i<allVecs[vecIndex].size() && vecIndex < allVecs.size(); i++){...} 

Edit: Cependant, cela ne donne pas encore la sortie correcte.

Answer 6

Votre fonction détermine toutes les combinaisons correctes mais celles-ci sont perdues car vous ne les agrégez pas correctement.

Je vois que vous avez posé la même question here. Je vais supposer que vous cherchez maintenant un moyen de ramener la production au niveau supérieur afin que vous puissiez le gérer à partir de là.

Le problème se résume alors à la façon dont vous regroupez la sortie. Vous utilisez une chaîne, mais recherchez plusieurs lignes de données. Il y a des réponses infinies à ceci. En voici une qui utilise un conteneur de vecteurs.

#include <iostream> 
#include <vector> 
#include <fstream> 
#include <sstream> 
using namespace std; 

void printAll(const vector<string> data); 

void EnumAll(const vector<vector<string> > &allVecs, size_t vecIndex, vector<string>&allStr, string strSoFar) 
{ 
    if (vecIndex >= allVecs.size()) 
    { 
     allStr.push_back(strSoFar); 
     return; 
    } 
    for (size_t i=0; i<allVecs[vecIndex].size(); i++) 
     EnumAll(allVecs, vecIndex+1, allStr, strSoFar+allVecs[vecIndex][i]); 
} 


int main (int arg_count, char *arg_vec[]) { 

    vector <string> Vec1; 
      Vec1.push_back("T"); 
      Vec1.push_back("C"); 
      Vec1.push_back("A"); 

    vector <string> Vec2; 
      Vec2.push_back("C"); 
      Vec2.push_back("G"); 
      Vec2.push_back("A"); 

    vector <string> Vec3; 
      Vec3.push_back("C"); 
      Vec3.push_back("G"); 
      Vec3.push_back("T"); 


    vector <vector<string> > allVecs; 

    allVecs.push_back(Vec1); 
    allVecs.push_back(Vec2); 
    allVecs.push_back(Vec3); 



    vector<string> allStr; 
    EnumAll(allVecs,0,allStr,""); 

    // print the string or process it with other function. 
    printAll(allStr); 

    return 0; 
} 

void printAll(const vector<string> data) 
{ 
    vector<string>::const_iterator c = data.begin(); 
    while(c!=data.end()) 
    { 
     cout << *c << endl; 
     ++c; 
    } 

}