Solve all 2d string vector combinations without using recursion? (C++ )

Question

The problem is:

Create a function that computes all combinations of an array of arrays of strings, e.g.: { { "red", "wooden", "gate" }, { "lazy", "little", "man" }, { "what", "where", "who", "why" } } to output: red lazy what, red lazy where, red lazy who, red lazy why, red little what, etc.....

This function will print all combinations of one word from the first array, one word from the second array, one word from the third array, etc.

Your solution may not use recursion

NOTE: the number of arrays and number of elements within each array may vary! Your method needs to be able to handle this.

---

I'm trying to practice my algorithms and this problem is just driving me crazy. I've tried brainstorming a few things but at this point, have spent hours getting nowhere. I was reworking my thoughts into another nested loop (see below...) when it occurred to me that maybe I just need to create a vector of strings (this would become a very large vector though...for now, lets call this vector endings). If I traverse backward in the outer vector of the given vector<vector<string>> and update endings by attaching each ending to each string in the current outer vector, then by the time I get to the first outer vector, all of my combinations will be in endings.

I probably didn't think of this immediately because I assumed if I was only printing, I shouldn't be storing so much. Anyway, here is some botched code that I stopped working on to post this. It's not much.

vector<vector<string>> ar = {{"red", "wooden", "gate"}, 
                             {"lazy", "little", "man"}, 
                             {"what", "where", "who", "why"}};

vector<string> res(ar.size());

for (int i = 0; i < ar.size(); i++) {   
    res[i]= ar[i][0];
}

int i;

for (i = ar.size()-1; i > 0; i--) {
    for (int j = arr.size()-1-i, j > arr.size()-1-i; j--) {
                // ...
    }
}

Let me know how you suggest solving this problem.

Answer 1

"All problems in computer science can be solved by another level of indirection" - David Wheeler

https://en.wikipedia.org/wiki/Indirection

#include <string>
#include <vector>
#include <iostream>

void print(std::vector<std::vector<std::string>> const& astrs, std::vector<std::size_t> const& idxs)
{
    const char* sep = "";
    for(std::size_t i = 0 ; i < astrs.size() ; ++i)
    {
        std::cout << sep << astrs[i][idxs[i]];
        sep = ", ";
    }
    std::cout << '\n';
}

bool next_in_sequence(std::vector<std::vector<std::string>> const& astrs, std::vector<std::size_t>& idxs)
{
    for(std::size_t i = astrs.size() ; i-- ; )
    {
        if(++idxs[i] != astrs[i].size())
        {
            return true;
        }
        idxs[i] = 0;
    }

    return false;
}

int main()
{
    std::vector<std::vector<std::string>> const ar = {
        {"red", "wooden", "gate"}, 
        {"lazy", "little", "man"}, 
        {"what", "where", "who", "why"}
    };

    vector<std::size_t> idxs(ar.size(), 0);

    do
    {
        print(ar, idxs);
    }
    while(next_in_sequence(ar, idxs));
}

This solution builds an array of indecies. Think of this array as an integer where each digit column has its own base. The base is the number of strings in the corresponding 'slot' in ar + 1.

All we need to do is "increment" the "integer" until it wraps. This is performed in the function next_in_sequence().

Here is another way of expressing this idea. It's conceptually less efficient (in reality, maybe not for 'small' input sets), but demonstrates the idea the other way around - compute the maximum number of combinations, iterate through each one and compute the 'digits' of our multi-base index representation as we go. It requires no additional storage, at the expense of repeating computations:

#include <string>
#include <vector>
#include <iostream>

std::size_t combinations_at(std::vector<std::vector<std::string>> const& astrs, std::size_t col)
{
    std::size_t result = 1;
    while (col != astrs.size())
    {
        result *= astrs[col].size();
        ++col;
    }
    return result;
}

void print(std::vector<std::vector<std::string>> const& astrs, std::size_t which)
{
    const char* sep = "";
    for(std::size_t col = 0 ; col != astrs.size() ; ++col)
    {
        auto nextmod = combinations_at(astrs, col + 1);
        auto i = which / nextmod;
        which %= nextmod;
        std::cout << sep << astrs[col][i];
        sep = ", ";
    }
    std::cout << '\n';
}

int main()
{
    std::vector<std::vector<std::string>> const ar = {
        {"red", "wooden", "gate"},
        {"lazy", "little", "man"},
        {"what", "where", "who", "why"}
    };

    const auto limit = combinations_at(ar, 0);
    for(std::size_t i = 0 ; i < limit ; ++i)
        print(ar, i);
}