Comment créer des combinaisons de plusieurs vecteurs sans boucles de codage en dur C ++?
https://stackoverflow.com/questions/1700079
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai plusieurs données qui ressemble à ceci:
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.
Ce que je veux faire est de créer toutes les combinaisons d'éléments dans Vecteur1 par des VectorK. Par conséquent, dans la fin, nous espérons obtenir cette sortie (en utilisant 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
Le problème que j'ai maintenant est que le code suivant de la mine fait que par les boucles hardcoding. Étant donné que nombre de vecteurs peut varier, nous devons trouver un moyen flexible pour obtenir le même résultat. Y at-il?
Ce code de la mine ne peut gérer jusqu'à 3 vecteurs (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;
}
La solution
fera l'affaire:
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]);
}
Appel avec:
printAll(allVecs, 0, "");
Autres conseils
Vous pouvez implémenter cela comme un compteur kilométrique, ce qui conduit les suivantes (œuvres pour les vecteurs de différentes tailles):
Disons que vous avez des vecteurs K dans un tableau v: v[0], v[1], ... v[K-1]
Gardez un tableau de itérateurs it (taille K) dans vos vecteurs, en commençant par it[i] = v[i].begin(). Gardez incrémenter it[K-1] dans une boucle. Lorsqu'un iterator frappe le end() du vecteur correspondant, vous l'enrouler autour de begin() et incrémenter l'itérateur précédent aussi (donc quand it[K-1] enroule autour, vous incrémentez it[K-2]). Ces augmentations peuvent « cascade » de sorte que vous devez les faire dans une boucle en arrière. Lorsque it[0] s'enroule autour, vous avez terminé (si votre condition de la boucle pourrait être quelque chose comme while (it[0] != v[0].end())
Mettre tout cela ensemble, la boucle qui fait le travail (après la mise en place des itérateurs) doit être quelque chose comme:
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 vous êtes intéressé par la complexité, le nombre d'incréments de itérateur qui se réaliser est facile à calculer. Par souci de simplicité ici je suppose que chaque vecteur est la même longueur N. Le nombre total de combinaisons est N K . Le dernier iterator s'incrémentée à chaque fois, de sorte que est N K , et se déplaçant à travers les itérateurs ce nombre se divise par N chaque fois, nous avons donc N K + N K-1 + ... N 1 ; cette somme est égale à N (N K - 1) / (N-1) = O (N K ). Cela signifie également que le coût amorti par-combinaison est O (1).
Quoi qu'il en soit, en bref, le traiter comme un odomètre tourner ses roues chiffres.
A C ++ 0x solution. A condition, bien sûr, votre compilé le supporte (actuellement 4.5 GCC et VS2010, je pense).
Les compiles suivants et fonctionne avec GCC 4.5 en utilisant le commutateur de -std=c++0x. L'utilisation de modèles variadique permet de combiner nombre arbitraire de conteneurs. Je suis sûr que vous pouvez trouver une solution plus idiomatiques.
#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 difficulté de base avec récursion est que vous devez garder une trace de la liste complète des indices (ou construire autre la chaîne progressivement, comme une autre question souligne).
Un moyen rapide de traiter ce problème sans la construction d'objets supplémentaires à l'intérieur des boucles est à portée de main votre fonction récursive un vecteur d'indices, de la même longueur que le vecteur de vecteurs:
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 combinaison de trois vecteurs est essentiellement la même que la première combinaison de deux vecteurs, puis en combinant le troisième avec le résultat.
Alors, tout se résume à écrire une fonction qui peut combiner deux vecteurs.
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;
}
Et puis quelque chose comme:
std::vector< std::string > result = combine(Vec1, Vec2);
result = combine(result, Vec3);
et ainsi de suite pour tous les vecteurs dont vous avez besoin combinées.
Notez qu'il est plus le « C ++ façon » d'utiliser l'entrée et de sortie itérateurs i.s.o. passant des vecteurs autour, et beaucoup plus efficace. Dans la version ci-dessus le vecteur est copié à plusieurs reprises ...
J'ai simplement vecteurs utilisés pour rester plus près de votre code original et, espérons-le, plus de sens pour vous.
Puisque vous semblez vouloir chaque sortie soit la longueur des vecteurs individuels, et vous semblez savoir que chaque vecteur est de 3 éléments de large
#Note also that the member of each vector is always 3.
à l'aide récursion pour une solution générale semble un peu exagéré ici.
Vous pouvez utiliser quelque chose comme ça:
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]);
}
}
}
}
Je suis trop intéressé par la construction d'une sorte de facile à rincer et répéter combinatoires. Je connais l'approche de type entraîné du compteur kilométrique, si vous voulez, où vous avez des indices à pied. Quelque chose le long de ces lignes. Le point est, de construire facilement les lignes dans d'un ensemble arbitraire de vecteurs non apparentés.
Cela ne répond pas tout à fait votre question, je ne pense pas, mais vous pouvez construire des combinaisons de temps statiques / conception utilisant une production variadique comme les suivantes, où T1-3 sont des types arbitraires:
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) {
}
En supposant que vous avez un vecteur qui ressemble à ceci:
typedef vector<tuple<T1, T2, T3>> CombosVector;
CombosVector combos;
push_back_tupled_combos(combos
, 1, 2, 3
, 4, 5, 6
, 7, 8, 9, ...);
Comme je l'ai dit, c'est une considération de temps de conception. Il ne construit pas tuples sur une plage de temps de fonctionnement des vecteurs. C'est le côté vers le bas. Le bon côté, cependant, est que vous gagnez la compilation compréhension du temps de vos tuples vectorisées.
Encore une fois, pas tout à fait ce que vous, ou moi-même, êtes après, mais peut-être il aide à susciter des commentaires favorables.
Au-dessus de la solution printAll plantera lorsque les vecteurs sont de ne pas même taille.
fixe cette question:
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 façon la plus simple de procéder est d'utiliser la récursivité. La fonction aura une boucle en elle et appeler lui-même, se fusionnant avec la sortie de l'appel récursif. Bien sûr, récursivité peut être converti à l'itération si vous êtes inquiet au sujet de l'espace pile, mais au moins comme point de départ, la solution récursive sera probablement plus facile pour vous.
utiliser la fonction next_permutation mis en oeuvre dans std de stl
