¿Cómo crear combinaciones de varios vectores sin bucles de hardcoding en C++?

Question

Tengo varios datos que tiene este aspecto:

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. 

Lo que quiero hacer es crear todas las combinaciones de elementos en Vector1 a cabo a través de VectorK. Por lo tanto, al final, la esperanza de obtener esta salida (utilizando 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 

El problema que estoy teniendo ahora es que el siguiente código de la mina hace que hardcoding los bucles. Dado que la cantidad de vectores puede variarse, necesitamos una forma flexible de obtener el mismo resultado. ¿Hay alguno?

Este código mío sólo puede manejar hasta 3 Vectores (codificado):

#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

Esto va a hacer el truco:

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]); 
} 

llamada con:

printAll(allVecs, 0, ""); 

Answer 2

La manera más simple de abordar esto es el uso de la recursividad. La función tendrá un ciclo y se llamará a sí misma, fusionándose con la salida de la llamada recursiva. Por supuesto, la recursividad se puede convertir a iteración si le preocupa el espacio de la pila, pero al menos como punto de partida, la solución recursiva será más fácil para usted.

Answer 3

Combinar tres vectores es esencialmente lo mismo que combinar primero dos vectores, y luego combinar el tercero con el resultado.

De modo que todo se reduce a escribir una función que puede combinar dos vectores.

std::vector<std::string> combine(std::vector<std::string> const & inLhs, std::vector<std::string> const & inRhs) { 
    std::vector<std::string> result; 
    for (int i=0; i < inLhs.size(); ++i) { 
     for (int j=0; j < inRhs.size(); ++j) { 
      result.push_back(inLhs[i] + inRhs[j]); 
     } 
    } 
    return result; 
} 

Y entonces algo así como:

std::vector<std::string> result = combine(Vec1, Vec2); 
result = combine(result, Vec3); 

y así sucesivamente para todos los vectores que necesita combinado.

Tenga en cuenta que es más la "forma C++" para utilizar los iteradores de entrada y salida i.s.o. pasando vectores alrededor, y mucho más eficiente. En la versión anterior, el vector se copia una y otra vez ...

Simplemente utilicé vectores para estar más cerca de su código original y, con suerte, tener más sentido para usted.

Answer 4

La dificultad básica con recursividad aquí es que usted necesita para realizar un seguimiento de toda la lista de índices (o bien construir la cadena incrementalmente, como señala otra pregunta).

Una manera conveniente de manejar este problema sin construir objetos adicionales dentro de los bucles es la mano de su función recursiva un vector de índices, de la misma longitud que el vector de vectores:

void printcombos(const vector<vector<string> >&vec,vector<int>&index,int depth) { 
    if(depth==index.length()) { 
    for(int i=0; i<depth; ++i) { 
     cout<<vec[i][index[i]]; 
    } 
    cout<<endl; 
    } else { 
    const vector<string> &myvec= vec[depth]; 
    int mylength= myvec.length(); 
    for(int i=0; i<mylength; ++i) { 
     index[depth]=i; 
     printcombos(vec,index,depth+1); 
    } 
    } 
} 

Answer 5

A C++ 0x solución. Siempre que, por supuesto, su compilado lo soporte (actualmente GCC 4.5 y VS2010, creo).

Lo siguiente compila y funciona con GCC 4.5 usando el interruptor -std=c++0x. El uso de plantillas variadic permite combinar una cantidad arbitraria de contenedores.Estoy seguro de que puedes encontrar una solución más idiomática.

#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 6

Uso función next_permutation implementado en std de STL

Answer 7

Ya que parece querer cada salida sea la longitud de los vectores individuales, y que parece saber que cada vector es 3 elementos de ancho de

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

utilizando la recursividad para una solución general parece un poco exagerado aquí.

Usted puede usar algo así:

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]); 
      } 
     } 
    } 
} 

Answer 8

se puede implementar esta como un odómetro, lo que lleva a la siguiente (trabaja para diferentes tamaños de vectores):

Digamos que tiene vectores de K en una matriz v: v[0], v[1], ... v[K-1]

Mantenga una matriz de iteradores it (tamaño K) en sus vectores, comenzando por it[i] = v[i].begin(). Siga incrementando it[K-1] en un bucle. Cuando un iterador golpea el end() del vector correspondiente, lo envuelve alrededor de begin() e incrementa el iterador anterior también (de modo que cuando it[K-1] se envuelve, se incrementa it[K-2]). Estos incrementos pueden "cascada", por lo que debe hacerlos en un ciclo hacia atrás. Cuando it[0] se envuelve alrededor, ya está hecho (por lo que su condición de bucle podría ser algo como while (it[0] != v[0].end())

poner todo eso junto, el bucle que hace el trabajo (después de configurar los iteradores) debe ser algo como:

while (it[0] != v[0].end()) { 
    // process the pointed-to elements 

    // the following increments the "odometer" by 1 
    ++it[K-1]; 
    for (int i = K-1; (i > 0) && (it[i] == v[i].end()); --i) { 
    it[i] = v[i].begin(); 
    ++it[i-1]; 
    } 
    } 

Si le interesa la complejidad, el número de incrementos de iterador que se realizan es fácil de calcular. Para simplificar, supongo que cada vector tiene la misma longitud N. El número total de combinaciones es N ^K. El último iterador se incrementa cada vez, por lo que es N ^K, y se mueve de vuelta a través de los iteradores este recuento se divide por N cada vez, entonces tenemos N ^K + N ^K-1 + ... N ; esta suma es igual a N (N ^K - 1)/(N-1) = O (N ^K). Esto también significa que el costo amortizado por combinación es O (1).

De todos modos, en pocas palabras, trátelo como un odómetro girando sus ruedas de dígitos.

Answer 9

Yo también estoy interesado en construir algún tipo de enjuague fácil y repetir combinatoria. Estoy familiarizado con el enfoque de tipo accionado por odómetro, si se quiere, donde tienes índices de marcha. Algo en esa línea. El punto es, construir fácilmente las tuplas a través de un conjunto arbitrario de vectores no relacionados.

Esto no acaba de responder a su pregunta, no creo, pero se podría construir diseño combinaciones estáticas/tiempo usando una producción variadic como el siguiente, donde T1-3 son tipos arbitrarios:

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) { 
} 

Suponiendo que tienes un vector que se ve algo como esto:

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

CombosVector combos; 

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

como dije, esta es una consideración durante el diseño. No construye tuplas en un rango de tiempo de ejecución de vectores. Ese es el lado negativo. El lado positivo, sin embargo, es que obtienes compilación en tiempo de compilación de tus tuplas vectorizadas.

Una vez más, no del todo lo que usted, o incluso yo, buscamos, pero tal vez ayuda a generar comentarios favorables.