c++algorithmvectorcombinationscartesian-product

How can I create the cartesian product of a vector of vectors?


I've a vector of vectors say vector<vector<int>> of different sizes as follows:

vector<vector<int>> items = {
    { 1, 2, 3 },
    { 4, 5 },
    { 6, 7, 8 }
};

I want to create combinations in terms of Cartesian product of these vectors like

1,4,6
1,4,7
1,4,8
1,5,6
// ...
3,5,7
3,5,8

How can I do that?


Solution

  • First, I'll show you a recursive version.

    typedef std::vector<int> Vi;
    typedef std::vector<Vi> Vvi;
    
    // recursive algorithm to to produce cart. prod.
    // At any given moment, "me" points to some Vi in the middle of the
    // input data set. 
    //   for int i in *me:
    //      add i to current result
    //      recurse on next "me"
    void cart_product(
        Vvi& rvvi,  // final result
        Vi&  rvi,   // current result 
        Vvi::const_iterator me, // current input
        Vvi::const_iterator end) // final input
    {
        if(me == end) {
            // terminal condition of the recursion. We no longer have
            // any input vectors to manipulate. Add the current result (rvi)
            // to the total set of results (rvvvi).
            rvvi.push_back(rvi);
            return;
        }
    
        // need an easy name for my vector-of-ints
        const Vi& mevi = *me;
        for(Vi::const_iterator it = mevi.begin(); it != mevi.end(); it++) {
            // final rvi will look like "a, b, c, ME, d, e, f"
            // At the moment, rvi already has "a, b, c"
            rvi.push_back(*it);  // add ME
            cart_product(rvvi, rvi, me+1, end); add "d, e, f"
            rvi.pop_back(); // clean ME off for next round
        }
    }
    

    See full code at Compiler Explorer.

    Now, I'll show you the recursive iterative version that I shamelessly stole from @John :

    // Seems like you'd want a vector of iterators
    // which iterate over your individual vector<int>s.
    struct Digits {
        Vi::const_iterator begin;
        Vi::const_iterator end;
        Vi::const_iterator me;
    };
    typedef std::vector<Digits> Vd;
    void cart_product(
        Vvi& out,  // final result
        Vvi& in)  // final result
     
    {
        Vd vd;
        
        // Start all of the iterators at the beginning.
        for(Vvi::const_iterator it = in.begin();
            it != in.end();
            ++it) {
            Digits d = {(*it).begin(), (*it).end(), (*it).begin()};
            vd.push_back(d);
        }
        
        while(1) {
            // Construct your first product vector by pulling 
            // out the element of each vector via the iterator.
            Vi result;
            for(Vd::const_iterator it = vd.begin();
                it != vd.end();
                it++) {
                result.push_back(*(it->me));
            }
            out.push_back(result);
    
            // Increment the rightmost one, and repeat.
    
            // When you reach the end, reset that one to the beginning and
            // increment the next-to-last one. You can get the "next-to-last"
            // iterator by pulling it out of the neighboring element in your
            // vector of iterators.
            for(Vd::iterator it = vd.begin(); ; ) {
                // okay, I started at the left instead. sue me
                ++(it->me);
                if(it->me == it->end) {
                    if(it+1 == vd.end()) {
                        // I'm the last digit, and I'm about to roll
                        return;
                    } else {
                        // cascade
                        it->me = it->begin;
                        ++it;
                    }
                } else {
                    // normal
                    break;
                }
            }
        }
    }