Every combination of X numbers possible if we select one value from each of Y vectors

Question

If there is a formal name for this problem (or this is a duplicate and I haven't found the right question to look at) then pointing out what I should actually be searching for would also be appreciated! However, I haven't been able to find any discussion or approaches to this specific problem.

I'm trying to keep the question as simple as possible, if more details would help just let me know.

Say we have four random length vectors of int:

std::vector<int> v1 {1, 7, 5, 2};
std::vector<int> v2 {4, 2, 1};
std::vector<int> v3 {1, 9, 4, 6, 4, 1, 2};
std::vector<int> v4 {9, 4};

Out of these four vectors, I need to generate every possible combination where we select only one int from each source vector (v1 - v4) at a time. The result should be that we generate every possible N length number out of the source vectors where N = the number of source vectors (4 in this case).

A few of the possible combinations are very easy to generate, for example selecting just the first number out of each source vector:

1 4 1 9

Selecting the last number of each source vector:

2 1 2 4

Where I'm stuck is generating every single combination possible. I need every possible N length number that can be created by combining one int from each of the 4 source vectors.

Thank you!

Answer 1

Here is an answer with an arbitrary amount of input vectors:

See a configuration of indices as a number, composed of digits in different number systems. Then think about counting up a set of indices just like you would count up a regular number in some number system. For four vectors of sizes 3 5 2 5 countin up the index set 0 2 1 4 would result in 0 3 0 0, for example.

For the following code, I'll assume that your vectors are given within another vector, that is as vector<vector<int> >

Here with a class for indices:

class Indices {

private:
    vector<size_t> indices;
    vector<size_t> maximal_sizes;
    bool _max_reached;

public:

    Indices(const vector<vector<int> >& vectors) : indices(vectors.size(), 0), maximal_sizes(vectors.size()), _max_reached(false) {

        for(size_t i = 0; i < vectors.size(); i++){
            maximal_sizes[i] = vectors[i].size();
        }
    }

    const size_t& operator[] (const size_t i) const { return indices[i]; }
    bool max_reached() const { return max_reached; }

    void count_up() {

        size_t current = 0;
        while(current < indices.size()){
            indices[current]++;
            if(indices[current] >= maximal_sizes[current]){
                indices[current] = 0;
                current++;
            } else {
                return;
            }
        }
        _max_reached = true;
    }

}

(split this into header and source)

and use it like

inline void print(const vector<vector<int> >& vectors, const Indices& indices){

    for(size_t i = 0; i < vectors.size(); i++){
        cout << vectors[i][Indices[i]] << " ";
    }
    cout << endl;
}

void all_combinations(const vector<vector<int> >& vectors){

    Indices indices(vectors);

    while(not indices.max_reached()){
        print(vectors, indices);
        indices.count_up();
    }
}

(Probably not in exactly such a function, but you get the idea. Also, Indices is not really descriptive enough I think, but can't think of a good short name right now. The max_reached mechanic is somewhat bugging me, doesn't look elegant. If somebody has an idea for improving this, I'd love to hear.)

Answer 2

You are indeed describing the Cartesian product of your sets. Like an ordinary product of numbers, this is an operation on two things, but it can be applied successively on more than two things:

A x B x C x D = A x (B x (C x D))

That structure is key to understanding the problem. You can break it down into recursive sub-problems each involving just two sets. That way you can handle an arbitrary number of sets.

The program for solving the problem can be recursive as well, or it can be iterative. What follows is a semi-optimized recursive solution using lists of sets represented by vector<int>. Given a list of sets

A, ...

it calculates the Cartesian product of two things: A, and the Cartesian product of the rest of the sets:

A x (...)

You can rearrange this procedure to start at the base case and go upward, i.e. ((D x C) x B) x A. That way you can just use a loop rather than the recursive calls. But thinking about the recursive structure of the problem is a good way to organize your thoughts.

void cartesian_product( list< vector<int> > sets, list< vector<int> >& product) {
        if ( sets.empty() )
                return;

        // get first set
        auto& s = sets.front();

        // base case
        if ( ++begin( sets ) == end( sets ) ) {
                for ( auto k : s ) {
                        product.push_back( { k } );
                }
                return;
        }

        // get cartesian product of the rest of the sets
        cartesian_product( list< vector<int> >( ++begin( sets ), end( sets ) ), product );

        // make additional copies of product and append each element of first set to them
        list< vector<int> > additions;
        for ( auto k = ++begin( s ); k != end( s ); ++k ) {
                list< vector<int> > ad = product;
                for ( auto& x : ad ) {
                        x.push_back( *k );
                }
                additions.splice( end( additions ), ad );
        }

        // append the first element of the first set to the original product
        for ( auto& x : product ) {
                x.push_back( s.front() );
        }

        // append the additions to the final product
        product.splice( end( product ), additions );

        return;
}

---

Here's the rest of the program:

#include <cassert>
#include <iostream>
#include <list>
#include <vector>

using std::vector;
using std::list;
using std::cout;
using std::endl;

void cartesian_product( list< vector<int> > sets, list< vector<int> > &product);

int main( int argc, char *argv[] ) {
        list< vector<int> > sets = {
                {1, 7, 5, 2},
                {4, 2, 1},
                {1, 9, 4, 6, 4, 1, 2},
                {9, 4}
        };

        list< vector<int> > product;
        cartesian_product( sets, product );

        for ( auto& x : product ) {
                cout << "{ ";
                for ( auto k : x ) {
                        cout << k << " ";
                }
                cout << "}" << endl;
        }
}