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

Tengo varios datos que se ven así:

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 toda la combinación de elementos en Vector1 a través de VectorK. Por lo tanto, al final esperamos obtener esta salida (usando 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 mío lo hace mediante la encoding de los bucles. Dado que la cantidad de vectores puede variarse, necesitamos una forma flexible de obtener el mismo resultado. ¿Hay alguna?

Este código mío solo puede manejar hasta 3 vectores (codificados):

 #include  #include  #include  #include  using namespace std; int main ( int arg_count, char *arg_vec[] ) { vector  Vec1; Vec1.push_back("T"); Vec1.push_back("C"); Vec1.push_back("A"); vector  Vec2; Vec2.push_back("C"); Vec2.push_back("G"); Vec2.push_back("A"); vector  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; } 

Esto hará el truco:

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

Llamar con:

 printAll(allVecs, 0, ""); 

Puede implementar esto como un odómetro, que conduce a lo siguiente (funciona para vectores de diferentes tamaños):

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

Mantenga una matriz de iteradores (tamaño K) en sus vectores, comenzando con it[i] = v[i].begin() . Sigue incrementándolo it[K-1] en un bucle. Cuando un iterador golpea el end() del vector correspondiente, lo envuelve para begin() e incrementa también el iterador anterior (de modo que cuando it[K-1] ajusta, lo incrementa it[K-2] ). Estos incrementos pueden “cascada”, por lo que debe hacerlos en un ciclo hacia atrás. Cuando it[0] ajusta, has terminado (por lo que tu condición de ciclo podría ser algo así como while (it[0] != v[0].end())

Poniendo todo eso junto, el bucle que hace el trabajo (después de configurar los iteradores) debería ser algo así 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, es fácil calcular el número de incrementos de iterador que se realizan. 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 retrocediendo a través de los iteradores este conteo se divide por N cada vez, entonces tenemos N K + N K-1 + … N 1 ; esta sum 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 resumen, trátalo como un odómetro girando sus ruedas de dígitos.

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

La siguiente comstack y trabaja con GCC 4.5 utilizando -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  #include  #include  #include  #include  typedef std::vector myvec; // Base case. void combine2(const std::string &row) { std::cout << row << std::endl; } // Recursive variadic template core function. template 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 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 v4 = {"T", "C", "A"}; std::vector v5 = {'C', 'G', 'A'}; std::vector v6 = {1 ,2 ,3}; combine(v4); combine(v4, v5); combine(v4, v5, v6); return 0; } 

La dificultad básica con la recursión aquí es que necesita realizar un seguimiento de toda la lista de índices (o bien, construir la cadena de forma incremental, como señala otra pregunta).

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

 void printcombos(const vector >&vec,vector&index,int depth) { if(depth==index.length()) { for(int i=0; i &myvec= vec[depth]; int mylength= myvec.length(); for(int i=0; i 

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

Entonces, 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 luego algo como:

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

y así sucesivamente para cada vector que necesita combinado.

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

Simplemente usé vectores para estar más cerca de tu código original y, con suerte, tener más sentido para ti.

Como parece que quieres que cada salida sea la longitud de los vectores individuales, y pareces saber que cada vector tiene 3 elementos de ancho desde

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

usar recursión para una solución general parece un poco exagerado aquí.

Puedes usar algo como eso:

 typedef boost::array 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 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]); } } } } 

Yo también estoy interesado en construir algún tipo de enjuague fácil y repetir combinatorio. 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 responde completamente a su pregunta, no creo, pero podría construir combinaciones de tiempo estático / de diseño usando una producción variadica como la siguiente, donde T1-3 son tipos arbitrarios:

 template void push_back_tupled_combos(V& v) { // Variadic no-args no-op } template 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 void push_back_tupled_combos(V& v, Args... args) { } 

Suponiendo que tienes un vector que se ve así:

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

Como dije, esta es una consideración de tiempo de 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 comstackción en tiempo de comstackción de tus tuplas vectorizadas.

Nuevamente, no es exactamente lo que usted, o incluso yo, buscamos, pero tal vez ayuda a generar comentarios favorables.

La forma más sencilla de abordar esto es usar la recursión. 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 stack, pero al menos como punto de partida, la solución recursiva será más fácil para usted.

Use la función next_permutation implementada en std of stl