C++で行列に困惑しました

Question

私は単純な問題のように思えますが、私の人生にとってはわかりません。基本的に、私が探しているのは、特定の値が特定の位置にとどまる非対称行列のすべての順列を見つける方法です。これを説明する最も簡単な方法は、例を挙げて...

この行列で

a b c 
a 
b c 
d e f 

...我々は次のことを持っていると言うが、私たちは「最初の文字はどちらかであるすべての順列を見つける必要がありさ2番目の文字は 'a'、3番目の文字は 'b'または 'c'、4番目の文字は 'd'、 'e'または 'f'です。我々のアルゴリズムでは、マトリックスのサイズは事前には分かっていない。それはちょうど私の最初の例でもあること...

a 
b 
c 
d 

か...

a b c d 
e f g h 
i j k l 
m n o p 

、私は可能性があることを観察して見ることができますことができます：

aabd 
aabe 
aabf 
aacd 
aace 
aacf 
babd 
babe 
babf 
bacd 
bace 
bacf 
cabd 
cabe 
cabf 
cacd 
cace 
cacf 

しかし、 、私はアルゴリズムを理解できません。誰も私の頭の中でこのことを手助けすることができますか？私が前もってサイズを知っていたら、私はそれをすることができましたが、私はしません。私は再帰関数のように感じる答えですが、私はそれを見ることができません。

EDIT：ここまでは値を行列に入れるためのコードです。いくつかのケースでは、値はスタンドアロンであり、それ以外では、それは括弧に囲まれた、複数の値のセットに付属しています...

int CountTestCases(const string &iTestStr, const map<string::size_type, string::size_type> &iHashTable) 
{ 
    vector<vector<char>> charMatrix; 

    string::const_iterator strIt = iTestStr.begin(); 

    while(strIt != iTestStr.end()) 
    { 
     if(*strIt == '(') 
     { 
      ++strIt; 
      char c = *strIt; 
      vector<char> tmpVec; 
      tmpVec.push_back(c); 
      ++strIt; 

      while(*strIt != ')') 
      { 
       c = *strIt; 
       tmpVec.push_back(c); 
       ++strIt; 
      } 

      charMatrix.push_back(tmpVec); 
     } 

     else 
     { 
      char c = *strIt; 
      vector<char> tmpVec; 
      tmpVec.push_back(c); 
      charMatrix.push_back(tmpVec); 
     } 

     ++strIt; 
    } 

    return 0; 
} 

Answer 1

ストアのデータは、必ずvectorに多くのものを追加することができますvector<vector<char>>として以前はサイズを知る必要はありません。

はい、再帰を行う必要があります。すべてのレベルで、そのレベルに対応するベクトルから要素を選択し、次のレベルのために再帰的に呼び出します。あなたがベクトルを使い果たしたとき、あなたは解決策を持っています。ここで

Answer 2

は擬似コードです：

int main() 
{  
    vector<char> outputVec; 
    PassToNextLevel(0, outputVec); 
} 


function PassToNextLevel(int rowId, vector<char) outputVec) 
{ 
    for each char 'currChar' in the 'charMatrix[rowId]' 
    { 
     outputVec.push_back(currChar); 
     PassToNextLevel(rowId++, outputVec); // recursive call, pass by value 

     if(rowId == rowSize-1) { // last row 
     print outputVec; 
     } 
    }  
} 

Answer 3

Woohoo、私はそれをやりました！ここで私は私ではなく、文字列をchar型のスタックを使用することができることを私に発生しましたが、最終製品は、とにかく文字列である必要があるため、それはかなり面倒に思えた

void FindCartisian(const vector<vector<char>> &iCharMatrix, int iRow, string &iWord, vector<string> &iFinalWords) 
{ 
    //We've reached the end of the column, save the finished product and return 
    if(iRow + 1 > iCharMatrix.size()) 
    { 
     iFinalWords.push_back(iWord); 
     return; 
    } 

    //Iterate across the row 
    for(vector<char>::const_iterator it = iCharMatrix[iRow].begin(); it != iCharMatrix[iRow].end(); ++it) 
    { 
     //Append what is in this position 
     char c = *it; 
     iWord.append(1, c); 

     //Drill down recursively from here 
     FindCartisian(iCharMatrix, iRow + 1, iWord, iFinalWords); 

     //Erase the last thing we added 
     iWord.erase(iWord.end() - 1); 
    } 
} 

...を思い付いた関数であります最後にスタックを文字列に変換します。

大きなデータセットの場合、このことは遅くても可能です。それをより速くする方法に関するアイデア？