how to get all the possible combinations of vector c++

Question

i have a problem and i´ve been strugglingfor hours to solve it but i dont find the way.

I have a vector<vector<string>> mat which i dont know the size, the only thing i know is that there are the same number of strings on each vector. Now, what Im trying to do is to get all the possible combinations of those strings such like: Imagine that mat.size() = 3 and mat[0].size() = 3(remember, all the vectors have same number of strings, so it doesnt matter if make mat[0].size() or mat[3].size() ) what i would like is to get all the strings on this positions

0,0 0,1 0,2  
0,0 0,1 1,2
0,0 0,1 2,2
0,0 1,1 0,2 
0,0 1,1 1,2
0,0 1,1 2,2
0,0 2,1 0,2
0,0 2,1 1,2
0,0 2,1 2,2
1,0 0,1 0,2

And so on....

Each row will be stored on a new array/vector

Any idea?

EDIT(in case is not really clear):

Imagine that mat has the next data:

mat[0] ={aa,bb,cc}
mat[1] ={dd,ee,ff}
mat[2] ={gg,hh,ll}

what i want to get somehow is:

aa,bb,cc
aa,bb,ff
aa,bb,ll
aa,ee,cc
aa,ee,ff
aa,ee,ll
aa,hh,cc
aa,hh,ff
aa,hh,ll

And so on...

Answer 1

You basically want a nested for loop for each column of your matrix. But since the number of columns is dynamic, you can't really do that in line. What you can do is use a recursive function, with a for loop in it that iterates over the rows, and selects the column based on a parameter, which is incremented on each recursive call. Something like this:

void permute_impl(size_t width, std::vector<std::vector<int>> const &mat,
                  size_t column, std::vector<int> &prefix) {
  if (column < width) {
    for (auto &row : mat) {
      prefix.push_back(row[column]);
      permute_impl(width, mat, column + 1, prefix);
      prefix.pop_back();
    }
  } else {
    for (auto i : prefix)
      std::cout << i << ' ';
    std::cout << '\n';
  }
}

void permute(std::vector<std::vector<int>> const &mat) {
  if (mat.empty())
    return;
  std::vector<int> prefix;
  size_t N = mat[0].size();
  // assert that all rows are the same size
  for (auto &row : mat)
    assert(row.size() == N);
  permute_impl(N, mat, 0, prefix);
}

DEMO

Answer 2

vector<vector<string>> mat; // each interior vector has the same length
// populate mat somehow...

size_t width = mat.at(0).size();
vector<string> out(pow(mat.size(), width);

// each value of first column is repeated (rows^(cols-1)) times
size_t reps = out.size(); 
for (size_t col = 0; col < width; ++col) {
    reps /= width;
    for (size_t ii = 0; ii < out.size(); ++ii) {
        if (ii != 0) {
            out[ii].append(',');
        } else {
            out[ii].reserve(2 * width); // performance optimization
        }
        size_t row = ii / reps % mat.size();
        out[ii].append(mat[row][col]); // write one cell of output
    }
}

If we knew in advance that the strings had some fixed length, we could optimize the reserve() call, but I just assume each string has at least one character.

Answer 3

I had no time to solve this problem but I tried for 10 minutes and I think I can answer your question. I think that you want to find all the possible combinations. So my solution in such a few time that I had would be this:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// I define the vector<int> data type to be stored in the variable int_vector.
typedef vector<int> int_vector;

// The definition of the max index of the array.
#define N 3

// The Solve class.
class Solve{
    public:
        // The elements of an array! This is just for testing!
        const int num[N] = {1, 2, 3};
        // The length of the array. That means the index of the last element.
        const int length = N - 1;
        // The vector that stores the possible combinations.
        vector<int_vector> solution;

        // The create_combination function.
        void create_combinations(){

            // The queue to create the possible combinations.
            queue<int_vector> combinations;

            // A vector just to store the elements.
            vector<int> test;

            // I create the front vector of the queue.
            for(int i = 0; i <= length; i++){
                // I push back to the vector the i-element of the num array.
                test.push_back(num[i]);
            }

            // I push back to the queue the test vector.
            combinations.push(test);

            // This is just a variable to store some numbers laterin the loop.
            int number;
            // This loop runs forever EXCEPT if the condition that is refered in the if-statement later in te loop happens.
            while(1){
                // This creates the possible combinations and push them back to the solution variable.
                for(int sub_i = 0; sub_i <= length - 1; sub_i++){
                    // I access the front element of the queue.
                    test = combinations.front();
                    number = test[sub_i];
                    test.erase(test.begin() + sub_i);
                    test.push_back(number);
                    combinations.push(test);
                    solution.push_back(test);
                }
                // The pop function erases the front element of the queue. That means that the next element of the queue becomes the front of the queue.
                combinations.pop();
                //This is the condition that breaks the loop if it is true.
                if(combinations.front()[2] == num[2]){
                    break;
                }
            }   
        }
};

// The main function.
int main(){
    // I create the object of the Solve class.
    Solve solve;
    // I call the create_combinations function of the Solve class.
    solve.create_combinations();
    // I access the solution variable of the Solve class and I store it to another variable called combinations.
    vector<int_vector> combinations = solve.solution;
    // This loop prints out to the screen the possible combinations
    for(int i = 0; i <= 5; i++){
        for(int sub_i = 0; sub_i <= solve.length; sub_i++){
            cout << combinations[i].at(sub_i) << " ";
        }
        cout << endl;
    }

    return 0;
}

As you can see I solved it using a queue and I store the combinations in a vector.