Create all possible combinations of multiple vectors

Question

I would like to create the combinations of several vectors

vector<int> Vec1;
Vec1.push_back(1);
Vec1.push_back(2);
Vec1.push_back(3);

vector <int> Vec2;
Vec2.push_back(5);
Vec2.push_back(6);
Vec2.push_back(7);
Vec2.push_back(8);

vector <int> Vec3;
Vec3.push_back(11);
Vec3.push_back(12);
Vec3.push_back(13);

vector<vector<int>> xt;
xt.push_back(Vec1);
xt.push_back(Vec2);
xt.push_back(Vec3);

The results should be something like

1 5 11
1 5 12
...
3 8 13

I could use nest loop for a given number of vectors. However, I am trying to write a function, like void printAll(const vector > &xt) I did find something similar

Howto create combinations of several vectors without hardcoding loops in C++?

But I am struggling converting it into int. Please offer me some suggestions.

Which part of the conversion to `int` are you having a problem with? — François Andrieux, Jan 15 '18 at 21:04
Possible duplicate of [Implementing an iterator over combinations of many vectors](https://stackoverflow.com/questions/46568287/implementing-an-iterator-over-combinations-of-many-vectors) — AMA, Jan 15 '18 at 21:40

score 4 · Accepted Answer · answered Jan 15 '18 at 22:47

Rather than a recursive function (which works, but can be clumsy in practice) I prefer to treat this as a simple problem of counting.

Let's start with a simplifying assumption: that we have 3 arrays of 10 elements apiece. In this case, it's obvious that we can print out all combinations simply by counting from 0 (which we'd think of as 000) to 999, and using each digit as a subscript into the appropriate sub-vector.

There's no magic to having 10 items per sub-vector, or having the same number of items in each sub-vector. It just happens that with 10 items apiece, the index into each array corresponds to the digits we're accustomed to seeing/using in base 10 numbers.

When we're dealing with base 10 numbers, we can use the remainder after division by 10 to get each digit we need. For the task at hand, we can do roughly the same, except that we use division by the number of elements in a sub-array instead.

So, let's start by computing the number of combinations in the inputs (for the moment, we'll assume each sub-vector has a non-zero size):

size_t max = 1;

for (auto const &v : allVecs)
    max *= v.size();

Then we simply count from 0 to max, take the remainder after dividing by the respective vector size, and using those to index into the sub-vectors:

for (size_t i=0; i<max; i++) {
    auto temp = i;
    for (auto const &vec : allVecs) {
        auto index = temp % vec.size();
        temp /= vec.size();
        std::cout << vec[index] << ' ';
    }
    std::cout << '\n';
}

As it stands right now, this has one point that might find confusing or problematic: it prints out the results in the reverse of the order you might expect. For example, instead of the 1 5 11 you show as the first output, it would show 11 5 1. If this is unacceptable, there are a number of easy ways to rectify the situation. The easiest is probably to start by simply reversing the input vector:

std::reverse(allVecs.begin(), allVecs.end());

If you have any hope of generating the combinations to ever finish, the input vector is going to be small enough for this O(N) operation to have little effect on anything.

Thank you so much. I believe your idea is right. It is better to treat it as a counting problem. — Jie Xue, Jan 16 '18 at 14:18

score 0 · Answer 2 · answered Jan 15 '18 at 21:16

You can simply convert it the proposed algorithm into int using std::to_string().

void printAll(const std::vector<std::vector<int> > &allVecs, size_t vecIndex, std::string strSoFar)
{
    if (vecIndex >= allVecs.size())
    {
        std::cout << strSoFar << std::endl;
        return;
    }
    for (size_t i=0; i<allVecs[vecIndex].size(); i++)
        printAll(allVecs, vecIndex+1, strSoFar+std::to_string(allVecs[vecIndex][i]));
}

Create all possible combinations of multiple vectors

2 Answers2