CODEWITHSUNDEEP
c++algorithmmatrix
David Sumich
David Sumich

Reputation: 55

Stumped by Matrix in C++

I have what seems like a simple problem, but for the life of me, I can't figure it out. Basically, what i am looking for is how to find all permutations of a non-symmetrical matrix, where certain values have to remain in certain positions. The simplest way to explain this is with an example...

Let's say we have the following...

a b c
a
b c
d e f

In this matrix, we have to find all permutations where the first letter is either 'a', 'b', or 'c', the second letter is 'a', the third letter is 'b' or 'c', and the fourth letter is 'd', 'e' or 'f'. In our algorithm, the size of the matrix is not known ahead of time. It could just as well be...

a
b
c
d

or...

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

In my first example, I can see through observation that the possibilities are:

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

However, I just can't figure out the algorithm. Can anybody help me get my head around this? If I knew the sizes ahead of time, I could do it, but I don't. I feel like a recursive function is the answer, but I just can't see it.

EDIT: Here is the code I have so far to get the values into a matrix. In some cases, the value is stand alone, and in others, it comes in sets of multiple values, surrounded by parenthesis...

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

Upvotes: 2

Views: 129

Answers (3)

David Sumich
David Sumich

Reputation: 55

Woohoo, I did it! Here is the function I came up with...

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

It occurred to me that I could use a char stack rather then a string, but since the final product has to be a string anyway, it seemed rather cumbersome to translate the stack to a string at the end.

For large data sets, this thing is slow as can be though. Any ideas on how to make it faster?

Upvotes: 0

vcp
vcp

Reputation: 962

Here is pseudo code:

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

Upvotes: 2

Sorin
Sorin

Reputation: 11968

Store the data as a vector<vector<char>> you can always add more things to a vector so you don't need to know the size before.

Yes, you need to do a recursion. At every level you pick an element from the vector corresponding to that level and call recursively for the next level. When you run out of vectors you have a solution.

Upvotes: 1

Related Questions