如何在遞歸函數中將字符串捕獲到變量中？

Question

我試圖打印幾個向量的所有可能的組合成員。爲什麼 下面的函數沒有按我的預期返回字符串？

#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; 
} 

的預期結果是：

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

下面是一個替代的解決方案。這不指望你通過什麼，但初始向量：此方法的

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. 
    } 
} 
} 

優勢： 這是遞歸的方面非常具有可讀性。它具有易於識別的遞歸基礎步驟以及遞歸本身。它的工作原理如下：遞歸的每次迭代枚舉n-1個向量中的所有可能的字符串，並且當前步驟簡單地列舉它們。

該方法的缺點： 1。enumAll（）函數被多次調用，返回相同的結果。 2.沉重的使用堆棧，因爲這不是尾遞歸。

我們可以通過執行以下操作來修復（1.），但除非我們消除尾遞歸，否則我們不能擺脫（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

你的函數不返回任何東西，因爲由於沒有return和你的函數結束最後通話不返回任何東西。

編輯： 一件事，你可以做的，是return之前，您ResultString到全局矢量每次插入。最後，您的所有結果都將在此向量中提供。

Answer 3

遞歸地調用EnumAll，但是忽略它返回的字符串。您必須決定如何彙總這些字符串 - 或者您將如何處理這些字符串。

Answer 4

你的第二個回報也應該以某種方式積累strSoFar。例如：

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

您提供的代碼崩潰。在以下行中，請注意您將超出vecIndex的限制。循環中沒有檢查它。此外，在上面的if條件中，您也不會重置vecIndex。所以你會有訪問衝突。

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

爲了解決這個問題，無論是在如果（）休息則VecIndex或使用語句如下：

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

編輯：但是，這並不能給出正確的輸出呢。

Answer 6

你的函數確定了所有正確的組合，但是由於你沒有正確地聚合它們而丟失了。

我看到你問了同樣的問題here。我會假設你現在正在尋找一種方法讓輸出回到頂層，以便你可以從那裏處理它。

然後問題歸結爲如何彙總輸出。您正在使用一個字符串，但正在查找多行數據。有無限的答案..這是一個使用矢量容器。

#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; 
    } 

}