Come creare combinazioni di più vettori, senza cicli di codifica dure in C ++?
https://stackoverflow.com/questions/1700079
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho diversi dati che assomiglia a questo:
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.
Quello che voglio fare è quello di creare tutte le combinazioni di elementi in Vettore1 attraverso fuori VectorK. Quindi, alla fine, speriamo di ottenere questa uscita (utilizzando 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
Il problema che sto avendo ora è che il seguente codice di mio fa che hardcoding i loop. Poiché il numero di vettori può essere variata, abbiamo bisogno di un modo flessibile per ottenere lo stesso risultato. C'è qualche?
Il codice della miniera può gestire solo fino a 3 Vettori (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;
}
Soluzione
Questo farà il trucco:
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]);
}
chiamata con:
printAll(allVecs, 0, "");
Altri suggerimenti
È possibile implementare questo come un contachilometri, che conduce ai seguenti lavori (per i vettori di diverse dimensioni):
Diciamo che avete vettori K in un array v: v[0], v[1], ... v[K-1]
Conservare una serie di iteratori it (dimensione K) nelle vostre vettori, a partire da it[i] = v[i].begin(). Mantenere incrementare it[K-1] in un ciclo. Quando una qualsiasi iteratore colpisce il end() del vettore corrispondente, si avvolge intorno al begin() e incrementare l'iteratore precedente anche (in modo che quando it[K-1] avvolge, si incrementa it[K-2]). Questi incrementi possono "a cascata" così si dovrebbe fare loro in un ciclo all'indietro. Quando it[0] avvolge, il gioco è fatto (in modo che le condizione del ciclo potrebbe essere qualcosa come while (it[0] != v[0].end())
Mettendo tutto insieme, il ciclo che fa il lavoro (dopo aver impostato i iteratori) dovrebbe essere qualcosa di simile:
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];
}
}
Se siete interessati a complessità, il numero di incrementi di iteratori che vengono eseguiti è facile da calcolare. Per semplicità qui Si assume ogni vettore è la stessa lunghezza N. Il numero totale di combinazioni è N K . L'ultimo iteratore viene incrementato ogni volta, così che è N K , e spostando indietro attraverso le iteratori questo conteggio viene diviso per N ogni volta, in modo da avere N K + N K-1 + ... N 1 ; questa somma è uguale a N (N K - 1) / (N-1) = O (N K ). Questo significa anche che il costo ammortizzato per-combinazione è O (1).
In ogni caso, insomma, trattarlo come un contachilometri girare le ruote cifre.
A C ++ 0x soluzione. A condizione, naturalmente, il vostro compilato supporta (attualmente GCC 4.5 e VS2010, credo).
I seguenti compila e lavora con GCC 4.5 utilizzando l'interruttore -std=c++0x. L'utilizzo di modelli variadic permette di combinare numero arbitrario di contenitori. Sono sicuro che si può trovare con una soluzione più idiomatica.
#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 difficoltà di base con la ricorsione è che è necessario tenere traccia di tutta la lista degli indici (oppure costruire la stringa in modo incrementale, come sottolinea un'altra questione).
Un espediente per gestire questo problema senza costruire oggetti aggiuntivi all'interno delle anse è consegnare la funzione ricorsiva un vettore di indici, della stessa lunghezza del vettore di vettori:
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);
}
}
}
Combinando tre vettori è essenzialmente lo stesso come prima combinazione di due vettori, e quindi combinando il terzo con il risultato.
Quindi, tutto si riduce a scrivere una funzione che può combinare due vettori.
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;
}
E poi qualcosa di simile:
std::vector< std::string > result = combine(Vec1, Vec2);
result = combine(result, Vec3);
e così via per ogni vettore avete bisogno combinato.
Si noti che è più il "++ modo C" per utilizzare l'ingresso e di uscita iteratori i.s.o. passando vettori intorno, e molto più efficiente. Nella versione di sopra del vettore viene copiato più e più volte ...
ho semplicemente usato vettori di stare più vicino al tuo codice originale e, si spera, più senso per voi.
Dal momento che sembra voler ogni uscita sia la lunghezza dei singoli vettori, e ti sembra di sapere che ogni vettore è larga 3 elementi da
#Note also that the member of each vector is always 3.
utilizzando la ricorsione per una soluzione generale sembra un po 'eccessivo qui.
Si può usare qualcosa di simile:
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]);
}
}
}
}
Anche io sono interessato a costruire una sorta di facile da lavare e ripetere combinatoria. Sono familiarità con il contachilometri approccio orientato tipo, se si vuole, dove hai ottenuto camminare indici. Qualcosa del genere. Il punto è, per costruire facilmente fuori le tuple attraverso un insieme arbitrario di vettori indipendenti.
Questa non abbastanza rispondere alla tua domanda, non credo, ma si potrebbe costruire combinazioni di tempo statico / progettazione utilizzando una produzione variadic come i seguenti, in cui T1-3 sono tipi arbitrari:
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) {
}
Supponendo che hai un vettore che sembra qualcosa di simile:
typedef vector<tuple<T1, T2, T3>> CombosVector;
CombosVector combos;
push_back_tupled_combos(combos
, 1, 2, 3
, 4, 5, 6
, 7, 8, 9, ...);
Come ho detto, questa è una considerazione i tempi di progettazione. Essa non costruisce tuple attraverso un intervallo di tempo di esecuzione di vettori. Questo è il lato verso il basso. Il lato alto, tuttavia, è che si guadagna tempo di compilazione comprensione dei tuoi tuple vectored.
Anche in questo caso, non proprio quello che, o anche io, sono dopo, ma forse aiuta innescare un feedback positivo.
Sopra PRINTALL soluzione sarà in crash quando i vettori sono di non stesse dimensioni.
Risolto quel problema:
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, "");
}
Il modo più semplice per avvicinarsi a questo è quello di utilizzare la ricorsione. La funzione avrà un loop in esso e chiamerà se stesso, si fonde con l'uscita della chiamata ricorsiva. Naturalmente, la ricorsione può essere convertito in iterazione, se siete preoccupati per lo spazio dello stack, ma almeno come punto di partenza, la soluzione ricorsiva sarà probabilmente più facile per voi.
Utilizzare la funzione next_permutation implementato in std di STL
