Get all combinations of elements of multidimensional array in C++

Question

Imagine a matrix with 3 rows and 3 columns containing the following elements:

     [,1] [,2] [,3]   
[1,]    1    4    7   
[2,]    2    5    8
[3,]    3    6    9

I would like to write a function that extracts every combination of triples with the first element from column1, the second element from column 2 etc. The first such triple might be

1,4,7, then
1,4,8
1,4,9
1,5,7
1,5,8 and so on

Each triple should be an argument to another function. In this example, there are 27 such triples, rows ^ columns in general.

While for this example, I could write 3 nested for loops iterating over the three columns, I would like to have a function that can handle any matrix with n rows and m columns.

In R, there is the expand.grid function available for this but I would like to have a plain C++ solution (without calling Rcpp).

If I have:

std::vector<double> col1 = {1,2,3};         
std::vector<double> col2 = {4,5,6};
std::vector<double> col3 = {7,8,9};
std::vector<std::vector<double>> matrix = {col1,col2,col3};

std::vector<std::vector<double>> result = generateGrid(matrix);
// result should contain [[1,4,7], [1,4,8], etc];

Answer 1

If I got it right, your problem is same as printing all n-tuples, where each element is in [0,m), which then will be indices to your m,n matrix .This can easily be done with recursion:

To print all n-tuples with elements from range [0,m):

for each number from [0,m):
 1. print number
 2. print all (n-1)-tuples with elements from range [0,m)

Which can be translated into following code:

#include <vector>
#include <iostream>

using row_t = std::vector<double>;
using matrix_t = std::vector<row_t>;


void function_impl(size_t col, size_t row, const size_t numCols, const size_t numRows, row_t& rBuff, const matrix_t& m, matrix_t& result)
{
    rBuff[col] = m[row][col];

    if (col == numCols - 1)//If we've filled the permutation, append it to result
        result.push_back(rBuff);
    else//Fill rest of row with all possible combinations
    {
        for (size_t r = 0; r < numRows; ++r)
            function_impl(col + 1, r, numCols, numRows, rBuff, m, result);
    }
}

matrix_t function(const matrix_t& m)
{
    size_t numRows = m[0].size();//Assumes rectangular matrix
    size_t numCols = m.size();

    matrix_t result;
    row_t rowBuffer(numCols);//Buffer to store current permutation of indices

    //Places all possible indices into first element of permutation and recurses
    for (size_t r = 0; r < numRows; ++r)
        function_impl(0, r, numCols, numRows, rowBuffer, m, result);
    return result;
}



int main()
{
    row_t col1 = {1,2,3};
    row_t col2 = {4,5,6};
    row_t col3 = {7,8,9};
    matrix_t matrix = {col1,col2,col3};

    //Prints all 27 combinations
    for (const auto& row : function(matrix))
    {
        for (const auto& el : row)
            std::cout << el << " ";
        std::cout << '\n';
    }
    system("PAUSE");
}

It does use recursion to depth of number of columns with constant one-row memory. Of course, resulting matrix will contain m^n elements, but if you just need to print them, you can do that immediately instead of appending to result and get rid of result matrix all together.