Как записать строку в переменную в рекурсивной функции?

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

Вы вызываете EnumAll рекурсивно, но игнорируете возвращаемую строку. Вы должны решить, как вы будете собирать эти строки или что вы будете делать с ними.

Answer 2

Ваша функция ничего не возвращает, потому что ваш последний вызов ничего не возвращает, так как нет return и конца вашей функции.

Edit: Одна вещь, которую вы можете сделать, это вставить ваш ResultString в глобальный вектор каждый раз перед return. И в конце все ваши результаты будут доступны в этом векторе.

Answer 3

Вот альтернативное решение. Это не ожидает, что вы передадите ничего, кроме начальных векторов:

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 4

Ваша функция определяет все правильные комбинации, но они теряются, поскольку вы не агрегируете их должным образом.

Я вижу, вы задали тот же вопрос здесь . Я предполагаю, что вы сейчас ищете способ вернуть вывод на верхний уровень, чтобы вы могли с ним справиться.

Тогда проблема сводится к тому, как вы агрегируете выходные данные. Вы используете строку, но ищете несколько строк данных. На это есть бесконечные ответы .. вот один, использующий векторный контейнер.

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

}

Answer 5

Код, который вы предоставили, вылетает. В следующей строке обратите внимание, что вы будете превышать пределы vecIndex. Там нет проверки на это в цикле. Кроме того, в приведенном выше условии if вы также не можете сбросить vecIndex. Таким образом, у вас будет нарушение прав доступа.

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

Чтобы исправить это, либо оставьте vecIndex в if (), либо используйте следующее для оператора:

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

Редактировать: Однако это еще не дает правильного вывода.

Answer 6

Ваш второй возврат также должен каким-то образом накапливать strSoFar. Что-то вроде:

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