c++ - 被 C++ 中的矩阵难住了

Question

我遇到了一个看似简单的问题，但我一生都无法解决。基本上，我正在寻找的是如何找到非对称矩阵的所有排列，其中某些值必须保留在某些位置。解释这一点的最简单方法是用一个例子......

假设我们有以下内容...

a b c
a
b c
d e f

在这个矩阵中，我们必须找到第一个字母是“a”、“b”或“c”，第二个字母是“a”，第三个字母是“b”或“c”的所有排列'，第四个字母是'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

但是，我就是无法弄清楚算法。有人能帮我解决这个问题吗？如果我提前知道尺寸，我就能做到，但我没有。我觉得递归函数就是答案，但我就是看不到它。

编辑:这是迄今为止我将值放入矩阵的代码。在某些情况下，该值是独立的，而在其他情况下，它以多个值的形式出现，并用括号括起来...

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

这是伪代码:

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