Howto create combinations of several vectors witho

Question

I have several data that looks like this:

Vector1_elements = T,C,A
Vector2_elements = C,G,A
Vector3_elements = C,G,T
..... up to ...
VectorK_elements = ...

#Note also that the member of each vector is always 3.

What I want to do is to create all combination of elements in Vector1 through out VectorK. Hence in the end we hope to get this output (using Vector1,2,3):

TCC
TCG
TCT
TGC
TGG
TGT
TAC
TAG
TAT
CCC
CCG
CCT
CGC
CGG
CGT
CAC
CAG
CAT
ACC
ACG
ACT
AGC
AGG
AGT
AAC
AAG
AAT

The problem I am having now is that the following code of mine does that by hardcoding the loops. Since number of Vectors can be varied, we need a flexible way to get the same result. Is there any?

This code of mine can only handle up to 3 Vectors (hardcoded):

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
using namespace std;


int main  ( int arg_count, char *arg_vec[] ) {

    vector <string> Vec1;
          Vec1.push_back("T");
          Vec1.push_back("C");
          Vec1.push_back("A");

    vector <string> Vec2;
          Vec2.push_back("C");
          Vec2.push_back("G");
          Vec2.push_back("A");

    vector <string> Vec3;
          Vec3.push_back("C");
          Vec3.push_back("G");
          Vec3.push_back("T");



     for (int i=0; i<Vec1.size(); i++) {
        for (int j=0; j<Vec2.size(); j++) {
            for (int k=0; k<Vec1.size(); k++) {
                cout << Vec1[i] << Vec2[i] << Vec3[k] << endl;
            }
        }
     }



    return 0;
}

Answer 1

Use next_permutation function implemented in std of stl

Answer 2

The simplest way to approach this is to use recursion. The function will have one loop in it and will call itself, merging itself with the output of the recursive call. Of course, recursion can be converted to iteration if you're worried about stack space, but at least as a starting point, the recursive solution will probably be easiest for you.

Answer 3

A C++0x solution. Provided, of course, your compiled supports it (currently GCC 4.5 and VS2010, I think).

The following compiles and works with GCC 4.5 using -std=c++0x switch. The use of variadic templates makes it possible to combine arbitrary number of containers. I am sure you can come up with a more idiomatic solution.

#include <vector>       
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>

typedef std::vector<std::string> myvec;

// Base case.
void combine2(const std::string &row) {
    std::cout << row << std::endl;
}

// Recursive variadic template core function.
template<class T0, class ...T>
void combine2(const std::string &row, const T0& cont0, T...cont_rest) {
    for (auto i = cont0.begin(); i != cont0.end(); ++i) {
        std::stringstream ss;
        ss << row << *i;
        combine2(ss.str(), cont_rest...);
    }
}

// The actual function to call.
template<class ...T>
void combine(T...containers) {
    combine2("", containers...);
}

int main() {
    myvec v1 = {"T", "C", "A"}, v2 = {"C", "G", "A"}, v3 = {"C", "G", "T"};

    combine(v1);
    combine(v1, v2);
    combine(v1, v2, v3);

    // Or even...
    std::vector<std::string> v4 = {"T", "C", "A"};
    std::vector<char> v5 = {'C', 'G', 'A'};
    std::vector<int> v6 = {1 ,2 ,3};

    combine(v4);
    combine(v4, v5);
    combine(v4, v5, v6);

    return 0;
}

Answer 4

This will do the trick:

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

Call with:

printAll(allVecs, 0, "");

Answer 5

I too am interested in building some sort of easy to rinse and repeat combinatorial. I am familiar with the odometer driven type approach, if you will, where you've got walking indices. Something along those lines. The point is, to easily build out the tuples across an arbitrary set of unrelated vectors.

This does not quite answer your question, I don't think, but you could build static/design time combinations using a variadic production such as the following, where T1-3 are arbitrary types:

template<class V>
void push_back_tupled_combos(V& v) {
  // Variadic no-args no-op
}

template<class V, typename A, typename B, typename C, typename... Args>
void push_back_tupled_combos(V& v, A a, B b, C c, Args... args) {
    v.push_back({ a, b, c });
    push_back_tupled_combos(v, args...);
}

template<class V, typename... Args>
void push_back_tupled_combos(V& v, Args... args) {
}

Assuming you've got a vector that looks something like this:

typedef vector<tuple<T1, T2, T3>> CombosVector;

CombosVector combos;

push_back_tupled_combos(combos
  , 1, 2, 3
  , 4, 5, 6
  , 7, 8, 9, ...);

Like I said, this is a design time consideration. It does not build tuples across a run time range of vectors. That's the down side. The up side, however, is that you gain compile time comprehension of your vectored tuples.

Again, not quite what you, or even I, are after, but maybe it helps spark favorable feedback.

Answer 6

Since you seem to want each output be the length of individual vectors, and you seem to know that each vector is 3 elements wide from

#Note also that the member of each vector is always 3.

using recursion for a general solution seems a bit overkill here.

You may use something like that :

typedef boost::array<std::string, 3> StrVec;
// basically your hardcoded version corrected (Vec2[j] not [i])
void printCombinations(const StrVec &Vec1,
                       const StrVec &Vec2,
                       const StrVec &Vec3) {
    for (int i=0; i<Vec1.size(); i++) {
        for (int j=0; j<Vec2.size(); j++) {
            for (int k=0; k<Vec3.size(); k++) {
                std::cout << Vec1[i] << Vec2[j] << Vec3[k] << std::endl;
            }
        }
    }
}

void foo() {
    typedef std::vector<StrVec> StrVecLvl2;
    StrVecLvl2 vecs;

    // do whatever with it ...

    // iterate with index instead of iterator only to shorten the code
    for (int i = 0; i < vecs.size(); ++i) {
        for (int j = i+1; j < vecs.size(); ++j) {
            for (int k = j+1; k < vecs.size(); ++k) {
                printCombinations(vecs[i], vecs[j], vecs[k]);
            }
        }
    }
}