Cómo crear combinaciones de varios vectores sin bucles de codificación dura en C ++?
https://stackoverflow.com/questions/1700079
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Tengo varios datos que se parece a esto:
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 esperamos conseguir 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 código de seguimiento de la mina hace que hardcoding los bucles. Dado que el número de vectores puede ser variada, necesitamos una forma flexible para obtener el mismo resultado. ¿Hay alguna?
Este código de mina sólo puede manejar hasta 3 Vectores (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;
}
Solución
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, "");
Otros consejos
Se puede implementar esto como un odómetro, lo que lleva a las siguientes obras (para los vectores de diferentes tamaños):
Supongamos que tiene vectores de K en una matriz v: v[0], v[1], ... v[K-1]
Mantener un conjunto de iteradores it (tamaño K) en sus vectores, a partir de it[i] = v[i].begin(). Mantenga incrementar it[K-1] en un bucle. Cuando cualquier iterador golpea el end() del vector correspondiente, que se envuelve alrededor de begin() e incrementar el iterador anterior también (por lo que cuando se envuelve alrededor de it[K-1], incrementas it[K-2]). Estos incrementos pueden "cascada", por lo que se debe hacer en un bucle hacia atrás. Cuando it[0] envuelve, ya está hecho (por lo que su condición de bucle podría ser algo como while (it[0] != v[0].end())
El 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 está interesado en la complejidad, el número de incrementos de iterador que consiguen realizar es fácil de calcular. Por simplicidad aquí voy a asumir cada vector es 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 hacia atrás a través de los iteradores este conteo se divide por N cada vez, por lo que tenemos N K + N K-1 + ... N 1 ; esta suma es igual a N (N K - 1) / (N-1) = O (N K ). Esto también significa que el coste amortizado per-combinación es O (1).
De todos modos, en definitiva, lo tratan como un odómetro girar sus ruedas dígitos.
A C ++ 0x solución. Siempre que, por supuesto, su compilado soporta (actualmente GCC 4.5 y VS2010, creo).
Los siguientes compila y funciona con GCC 4.5 con el interruptor -std=c++0x. El uso de plantillas variadic hace que sea posible combinar número arbitrario de contenedores. Estoy seguro de que puede llegar a 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;
}
La dificultad básica con recursividad aquí es que se necesita para realizar un seguimiento de toda la lista de índices (o bien construir la cadena de forma incremental, como otra cuestión señala).
Una manera conveniente de manejar este problema sin construir objetos adicionales dentro de los bucles es a 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);
}
}
}
La combinación de tres vectores es esencialmente la misma que la combinación de primero dos vectores, y luego la combinación de la tercera uno con el resultado.
Por lo tanto, 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 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 "C ++ camino" para utilizar la entrada y salida de los iteradores 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 usé vectores estar más cerca de su código original y, con suerte, tener más sentido para usted.
Ya que parece querer cada salida sea la longitud de los vectores individuales, y usted 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í.
Es posible 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]);
}
}
}
}
Yo también estoy interesado en la construcción de una especie de fácil de aclarar y repetir combinatoria. Estoy familiarizado con el enfoque de tipo odómetro impulsado, si se quiere, en el que tienes índices caminar. Algo por el estilo. El punto es, para 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) {
}
Si se asume 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 se acumula tuplas a través de un rango de tiempo de ejecución de los vectores. Ese es el lado negativo. El lado positivo, sin embargo, es que se gana la comprensión compilar momento de sus tuplas vectorizadas.
Una vez más, no es lo que usted, o incluso yo, está después, pero tal vez ayuda a provocar comentarios favorables.
Por encima de printAll solución se colgará cuando los vectores son del mismo tamaño no.
Fija esta cuestión:
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++)
{
if( i < allVecs[vecIndex].size() )
{
printAll(allVecs, vecIndex + 1, strSoFar + " " + allVecs[vecIndex][i]);
}
}
}
int main()
{
vector <string> Vec1;
Vec1.push_back("A1");
Vec1.push_back("A2");
Vec1.push_back("A3");
Vec1.push_back("A4");
vector <string> Vec2;
Vec2.push_back("B1");
Vec2.push_back("B2");
vector <string> Vec3;
Vec3.push_back("C1");
vector<vector<string> > allVecs;
allVecs.push_back(Vec3);
allVecs.push_back(Vec1);
allVecs.push_back(Vec2);
printAll(allVecs, 0, "");
}
La manera más simple de abordar esto es el uso de la recursividad. La función tendrá un bucle en ella y llamará a sí mismo, la fusión de sí mismo con la salida de la llamada recursiva. Por supuesto, la recursividad se puede convertir en iteración si usted está preocupado por espacio de pila, pero al menos como punto de partida, la solución recursiva probablemente será más fácil para usted.
Utilice la función next_permutation implementado en std de STL
