2

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;
}
David Sumich
  • 55
  • 4
  • 1
    *Permutation* means rearranging a fixed number of elements. However your sample output is different. You appear to be doing *Cartesian product*. – M.M May 24 '16 at 08:14
  • @M.M I think the OP wants to get all the matrices that differ from the original matrix by permutations over the lines. – Julien Lopez May 24 '16 at 08:17
  • @JulienLopez if that is true then the first answer would be `{a c b, a, b c, d e f}` which is not the same form as OP's quote `aabd` – M.M May 24 '16 at 08:18
  • @M.M I think `aabd`, `aabe`, ... refers to the first column – Julien Lopez May 24 '16 at 08:22
  • 1
    @M.M, I certainly might be misusing the word permutation, and if I am, I apologize for the confusion. However, I think you have the right idea of what I am looking for. – David Sumich May 24 '16 at 08:26
  • Just realized that is indeed the Cartesian product of the matrix. :) Shame on me. – Julien Lopez May 24 '16 at 08:30
  • @JulienLopez, the example above basically means that a "word" or permutation as I was calling it, can be made of 'a', 'b', 'c' as the first letter, 'a' as the second letter, 'a', 'b' as the third letter and 'd', 'e', 'f' as the fourth letter. Those are the only possibilities. From that, you can see there are 18 permutations or varieties if you will. 3 x 3 x 2 x 1 = 18. – David Sumich May 24 '16 at 08:31
  • May be helpful: http://stackoverflow.com/questions/30467698/c-cartesian-product-of-multiple-strings – M.M May 24 '16 at 09:40

3 Answers3

2

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; 
      }
    }     
}
vcp
  • 962
  • 7
  • 15
  • Awesome, I think I can grapple that. Thanks! – David Sumich May 24 '16 at 08:35
  • I might be missing something, but I think there is a bug in here: you should be removing the `currChar` from the `outputVec` at the end of your "for each"-loop. In the current state of the code, ALL the words will always start with `a`, because you never remove it. When you get to the `b` in the first line of the input file, you will have `ab` in your `outputVec`... – dingalapadum May 24 '16 at 09:35
  • and why do you pass the `outputVec` by value rather than by reference? – dingalapadum May 24 '16 at 09:42
  • @dingalapadum, I believe you are correct. If you look at my solution below, you can see that I erase the last thing added after returning from the recursion. – David Sumich May 24 '16 at 19:20
1

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.

Sorin
  • 11,863
  • 22
  • 26
0

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?

David Sumich
  • 55
  • 4