Come posso creare un prodotto cartesiano di vettori di vettori?

Ho un vettore di vettori che dice elementi vector<vector > items di dimensioni diverse come segue

 1,2,3 4,5 6,7,8 

Voglio creare combinazioni in termini di prodotto cartesiano di questi vettori come

 1,4,6 1,4,7 1,4,8 and so on till 3,5,8 

Come lo posso fare ? Ho cercato diversi link e li ho anche elencati alla fine di questo post, ma non sono in grado di interpretarlo poiché non sono così familiare con la lingua. Qualcuno potrebbe aiutarmi con questo.

 #include  #include  #include  using namespace std; int main() { vector<vector > items; int k = 0; for ( int i = 0; i < 5; i++ ) { items.push_back ( vector() ); for ( int j = 0; j < 5; j++ ) items[i].push_back ( k++ ); } cartesian ( items ); // I want some function here to do this. } 

Questo programma ha vettori di uguale lunghezza e lo metto in modo che sia più facile capire la mia struttura dati. Sarà molto utile anche se qualcuno usa altre risposte da altri link e si integra con questo per ottenere il risultato. Grazie mille

Un paio di collegamenti Ho guardato un programma Two da: programma

    Per prima cosa ti mostrerò una versione ricorsiva.

     // Cartesion product of vector of vectors #include  #include  #include  // Types to hold vector-of-ints (Vi) and vector-of-vector-of-ints (Vvi) typedef std::vector Vi; typedef std::vector Vvi; // Just for the sample -- populate the intput data set Vvi build_input() { Vvi vvi; for(int i = 0; i < 3; i++) { Vi vi; for(int j = 0; j < 3; j++) { vi.push_back(i*10+j); } vvi.push_back(vi); } return vvi; } // just for the sample -- print the data sets std::ostream& operator<<(std::ostream& os, const Vi& vi) { os << "("; std::copy(vi.begin(), vi.end(), std::ostream_iterator(os, ", ")); os << ")"; return os; } std::ostream& operator<<(std::ostream& os, const Vvi& vvi) { os << "(\n"; for(Vvi::const_iterator it = vvi.begin(); it != vvi.end(); it++) { os << " " << *it << "\n"; } os << ")"; return os; } // recursive algorithm to to produce cart. prod. // At any given moment, "me" points to some Vi in the middle of the // input data set. // for int i in *me: // add i to current result // recurse on next "me" // void cart_product( Vvi& rvvi, // final result Vi& rvi, // current result Vvi::const_iterator me, // current input Vvi::const_iterator end) // final input { if(me == end) { // terminal condition of the recursion. We no longer have // any input vectors to manipulate. Add the current result (rvi) // to the total set of results (rvvvi). rvvi.push_back(rvi); return; } // need an easy name for my vector-of-ints const Vi& mevi = *me; for(Vi::const_iterator it = mevi.begin(); it != mevi.end(); it++) { // final rvi will look like "a, b, c, ME, d, e, f" // At the moment, rvi already has "a, b, c" rvi.push_back(*it); // add ME cart_product(rvvi, rvi, me+1, end); add "d, e, f" rvi.pop_back(); // clean ME off for next round } } // sample only, to drive the cart_product routine. int main() { Vvi input(build_input()); std::cout << input << "\n"; Vvi output; Vi outputTemp; cart_product(output, outputTemp, input.begin(), input.end()); std::cout << output << "\n"; } 

    Ora ti mostrerò la versione iterativa ricorsiva che ho rubato spudoratamente a @John:

    Il resto del programma è praticamente lo stesso, mostrando solo la funzione cart_product .

     // Seems like you'd want a vector of iterators // which iterate over your individual vectors. struct Digits { Vi::const_iterator begin; Vi::const_iterator end; Vi::const_iterator me; }; typedef std::vector Vd; void cart_product( Vvi& out, // final result Vvi& in) // final result { Vd vd; // Start all of the iterators at the beginning. for(Vvi::const_iterator it = in.begin(); it != in.end(); ++it) { Digits d = {(*it).begin(), (*it).end(), (*it).begin()}; vd.push_back(d); } while(1) { // Construct your first product vector by pulling // out the element of each vector via the iterator. Vi result; for(Vd::const_iterator it = vd.begin(); it != vd.end(); it++) { result.push_back(*(it->me)); } out.push_back(result); // Increment the rightmost one, and repeat. // When you reach the end, reset that one to the beginning and // increment the next-to-last one. You can get the "next-to-last" // iterator by pulling it out of the neighboring element in your // vector of iterators. for(Vd::iterator it = vd.begin(); ; ) { // okay, I started at the left instead. sue me ++(it->me); if(it->me == it->end) { if(it+1 == vd.end()) { // I'm the last digit, and I'm about to roll return; } else { // cascade it->me = it->begin; ++it; } } else { // normal break; } } } } 

    Ecco una soluzione in C ++ 11.

    L’indicizzazione degli array di dimensioni variabili può essere eseguita in modo eloquente con l’aritmetica modulare.

    Il numero totale di righe nell’output è il prodotto delle dimensioni dei vettori di input. Questo è:

     N = v[0].size() * v[1].size() * v[2].size() 

    Pertanto il ciclo principale ha n come variabile di iterazione, da 0 a N-1 . In linea di principio, ogni valore di n codifica informazioni sufficienti per estrarre ciascuno degli indici di v per quella iterazione. Questo viene fatto in un subloop usando l’aritmetica modulare ripetuta:

     #include  #include  #include  #include  using namespace std; void cartesian( vector >& v ) { auto product = []( long long a, vector& b ) { return a*b.size(); }; const long long N = accumulate( v.begin(), v.end(), 1LL, product ); vector u(v.size()); for( long long n=0 ; n > v { { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } }; cartesian(v); return 0; } 

    Produzione:

     1 4 6 1 4 7 1 4 8 ... 3 5 8 

    Codice più breve:

     vector> cart_product (const vector>& v) { vector> s = {{}}; for (const auto& u : v) { vector> r; for (const auto& x : s) { for (const auto y : u) { r.push_back(x); r.back().push_back(y); } } s = move(r); } return s; } 

    Ecco la mia soluzione. Anche iterativo, ma un po ‘più corto di quello sopra …

     void xp(const vector*>& vecs, vector*> *result) { vector*>* rslts; for (int ii = 0; ii < vecs.size(); ++ii) { const vector& vec = *vecs[ii]; if (ii == 0) { // vecs=[[1,2],...] ==> rslts=[[1],[2]] rslts = new vector*>; for (int jj = 0; jj < vec.size(); ++jj) { vector* v = new vector; v->push_back(vec[jj]); rslts->push_back(v); } } else { // vecs=[[1,2],[3,4],...] ==> rslts=[[1,3],[1,4],[2,3],[2,4]] vector*>* tmp = new vector*>; for (int jj = 0; jj < vec.size(); ++jj) { // vec[jj]=3 (first iter jj=0) for (vector*>::const_iterator it = rslts->begin(); it != rslts->end(); ++it) { vector* v = new vector(**it); // v=[1] v->push_back(vec[jj]); // v=[1,3] tmp->push_back(v); // tmp=[[1,3]] } } for (int kk = 0; kk < rslts->size(); ++kk) { delete (*rslts)[kk]; } delete rslts; rslts = tmp; } } result->insert(result->end(), rslts->begin(), rslts->end()); delete rslts; } 

    L’ho derivato con un po ‘di dolore da una versione di haskell che ho scritto:

     xp :: [[a]] -> [[a]] xp [] = [] xp [l] = map (:[]) l xp (h:t) = foldr (\x acc -> foldr (\l acc -> (x:l):acc) acc (xp t)) [] h 

    Sembra che tu voglia un vector di iteratori che itera sui tuoi singoli vector s.

    Inizia tutti gli iteratori all’inizio. Costruisci il tuo primo vettore di prodotto estraendo l’elemento di ogni vettore tramite l’iteratore.

    Incrementare quello più a destra e ripetere.

    Quando raggiungi la fine, ripristina quella all’inizio e incrementa la penultima. È ansible ottenere l’iteratore “penultimo” estraendolo dall’elemento confinante nel proprio vettore di iteratori.

    Continua a pedalare fino a quando sia l’ultimo che il penultimo iteratore sono alla fine. Quindi, ripristinali entrambi, incrementa il terzo dall’ultimo iteratore. In generale, questo può essere messo in cascata.

    È come un contachilometri, ma con ogni cifra diversa in una base diversa.

    Poiché avevo bisogno della stessa funzionalità, ho implementato un iteratore che calcola il prodotto cartesiano al volo, se necessario, e lo itera su di esso.

    Può essere usato come segue.

     #include  #include  #include  #include "cartesian.hpp" int main() { // Works with a vector of vectors std::vector> test{{1,2,3}, {4,5,6}, {8,9}}; CartesianProduct cp(test); for(auto const& val: cp) { std::cout << val.at(0) << ", " << val.at(1) << ", " << val.at(2) << "\n"; } // Also works with something much less, like a forward_list of forward_lists std::forward_list> foo{{"boo", "far", "zab"}, {"zoo", "moo"}, {"yohoo", "bohoo", "whoot", "noo"}}; CartesianProduct bar(foo); for(auto const& val: bar) { std::cout << val.at(0) << ", " << val.at(1) << ", " << val.at(2) << "\n"; } } 

    Il file cartesian.hpp ha questo aspetto.

     #include  #include  #include  #include  #include  //! Class iterating over the Cartesian product of a forward iterable container of forward iterable containers template class CartesianProductIterator : public boost::iterator_facade, std::vector const, boost::forward_traversal_tag> { public: //! Delete default constructor CartesianProductIterator() = delete; //! Constructor setting the underlying iterator and position /*! * \param[in] structure The underlying structure * \param[in] pos The position the iterator should be initialized to. std::numeric_limits::max()stands for the end, the position after the last element. */ explicit CartesianProductIterator(T const& structure, std::size_t pos); private: //! Give types more descriptive names // \{ typedef T OuterContainer; typedef typename T::value_type Container; typedef typename T::value_type::value_type Content; // \} //! Grant access to boost::iterator_facade friend class boost::iterator_core_access; //! Increment iterator void increment(); //! Check for equality bool equal(CartesianProductIterator const& other) const; //! Dereference iterator std::vector const& dereference() const; //! The part we are iterating over OuterContainer const& structure_; //! The position in the Cartesian product /*! * For each element of structure_, give the position in it. * The empty vector represents the end position. * Note that this vector has a size equal to structure->size(), or is empty. */ std::vector position_; //! The position just indexed by an integer std::size_t absolutePosition_ = 0; //! The begin iterators, saved for convenience and performance std::vector cbegins_; //! The end iterators, saved for convenience and performance std::vector cends_; //! Used for returning references /*! * We initialize with one empty element, so that we only need to add more elements in increment(). */ mutable std::vector> result_{std::vector()}; //! The size of the instance of OuterContainer std::size_t size_ = 0; }; template CartesianProductIterator::CartesianProductIterator(OuterContainer const& structure, std::size_t pos) : structure_(structure) { for(auto & entry: structure_) { cbegins_.push_back(entry.cbegin()); cends_.push_back(entry.cend()); ++size_; } if(pos == std::numeric_limits::max() || size_ == 0) { absolutePosition_ = std::numeric_limits::max(); return; } // Initialize with all cbegin() position position_.reserve(size_); for(std::size_t i = 0; i != size_; ++i) { position_.push_back(cbegins_[i]); if(cbegins_[i] == cends_[i]) { // Empty member, so Cartesian product is empty absolutePosition_ = std::numeric_limits::max(); return; } } // Increment to wanted position for(std::size_t i = 0; i < pos; ++i) { increment(); } } template void CartesianProductIterator::increment() { if(absolutePosition_ == std::numeric_limits::max()) { return; } std::size_t pos = size_ - 1; // Descend as far as necessary while(++(position_[pos]) == cends_[pos] && pos != 0) { --pos; } if(position_[pos] == cends_[pos]) { assert(pos == 0); absolutePosition_ = std::numeric_limits::max(); return; } // Set all to begin behind pos for(++pos; pos != size_; ++pos) { position_[pos] = cbegins_[pos]; } ++absolutePosition_; result_.emplace_back(); } template std::vector const& CartesianProductIterator::dereference() const { if(absolutePosition_ == std::numeric_limits::max()) { throw new std::out_of_range("Out of bound dereference in CartesianProductIterator\n"); } auto & result = result_[absolutePosition_]; if(result.empty()) { result.reserve(size_); for(auto & iterator: position_) { result.push_back(*iterator); } } return result; } template bool CartesianProductIterator::equal(CartesianProductIterator const& other) const { return absolutePosition_ == other.absolutePosition_ && structure_ == other.structure_; } //! Class that turns a forward iterable container of forward iterable containers into a forward iterable container which iterates over the Cartesian product of the forward iterable containers template class CartesianProduct { public: //! Constructor from type T explicit CartesianProduct(T const& t) : t_(t) {} //! Iterator to beginning of Cartesian product CartesianProductIterator begin() const { return CartesianProductIterator(t_, 0); } //! Iterator behind the last element of the Cartesian product CartesianProductIterator end() const { return CartesianProductIterator(t_, std::numeric_limits::max()); } private: T const& t_; }; 

    Se qualcuno ha commenti su come renderlo più veloce o migliore, li apprezzerei molto.

    Sono stato costretto a implementarlo per un progetto a cui stavo lavorando e ho trovato il codice qui sotto. Può essere bloccato in un’intestazione e il suo utilizzo è molto semplice, ma restituisce tutte le combinazioni ottenibili da un vettore di vettori. La matrice restituita contiene solo numeri interi. Questa è stata una decisione consapevole perché volevo solo gli indici. In questo modo, ho potuto indicizzare ciascuno dei vettori del vettore e quindi eseguire i calcoli di cui chiunque avrebbe bisogno … meglio evitare di lasciare a CartesianProduct la stessa “roba”, è un concetto matematico basato sul conteggio non su una struttura dati. Sono abbastanza nuovo per c ++ ma questo è stato testato in un algoritmo di decrittazione abbastanza bene. C’è una leggera ricorsione, ma nel complesso si tratta di una semplice implementazione di un semplice concetto di conteggio.

     // Use of the CartesianProduct class is as follows. Give it the number // of rows and the sizes of each of the rows. It will output all of the // permutations of these numbers in their respective rows. // 1. call cp.permutation() // need to check all 0s. // 2. while cp.HasNext() // it knows the exit condition form its inputs. // 3. cp.Increment() // Make the next permutation // 4. cp.permutation() // get the next permutation class CartesianProduct{ public: CartesianProduct(int num_rows, vector sizes_of_rows){ permutation_ = new int[num_rows]; num_rows_ = num_rows; ZeroOutPermutation(); sizes_of_rows_ = sizes_of_rows; num_max_permutations_ = 1; for (int i = 0; i < num_rows; ++i){ num_max_permutations_ *= sizes_of_rows_[i]; } } ~CartesianProduct(){ delete permutation_; } bool HasNext(){ if(num_permutations_processed_ != num_max_permutations_) { return true; } else { return false; } } void Increment(){ int row_to_increment = 0; ++num_permutations_processed_; IncrementAndTest(row_to_increment); } int* permutation(){ return permutation_; } int num_permutations_processed(){ return num_permutations_processed_; } void PrintPermutation(){ cout << "( "; for (int i = 0; i < num_rows_; ++i){ cout << permutation_[i] << ", "; } cout << " )" << endl; } private: int num_permutations_processed_; int *permutation_; int num_rows_; int num_max_permutations_; vector sizes_of_rows_; // Because CartesianProduct is called first initially with it's values // of 0 and because those values are valid and important output // of the CartesianProduct we increment the number of permutations // processed here when we populate the permutation_ array with 0s. void ZeroOutPermutation(){ for (int i = 0; i < num_rows_; ++i){ permutation_[i] = 0; } num_permutations_processed_ = 1; } void IncrementAndTest(int row_to_increment){ permutation_[row_to_increment] += 1; int max_index_of_row = sizes_of_rows_[row_to_increment] - 1; if (permutation_[row_to_increment] > max_index_of_row){ permutation_[row_to_increment] = 0; IncrementAndTest(row_to_increment + 1); } } }; 
     #include  #include  void cartesian (std::vector> const& items) { auto n = items.size(); auto next = [&](std::vector & x) { for ( int i = 0; i < n; ++ i ) if ( ++x[i] == items[i].size() ) x[i] = 0; else return true; return false; }; auto print = [&](std::vector const& x) { for ( int i = 0; i < n; ++ i ) std::cout << items[i][x[i]] << ","; std::cout << "\b \n"; }; std::vector x(n); do print(x); while (next(x)); // Shazam! } int main () { std::vector> items { { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } }; cartesian(items); return 0; } 

    L’idea alla base di questo è la seguente.

    Sia n := items.size() .
    Sia m_i := items[i].size() , per tutti i in {0,1,...,n-1} .
    Sia M := {0,1,...,m_0-1} x {0,1,...,m_1-1} x ... x {0,1,...,m_{n-1}-1} .

    Per prima cosa risolviamo il problema più semplice di iterare attraverso M Questo è realizzato dal next lambda. L’algoritmo è semplicemente il “trasporto” che gli scolari di routine usano per aggiungere 1, anche se con un sistema di numeri radix misto.

    Usiamo questo per risolvere il problema più generale trasformando una tupla x in M in una delle tuple desiderate tramite gli items[i][x[i]] della formula items[i][x[i]] per tutti i in {0,1,...,n-1} . Eseguiamo questa trasformazione nella print lambda.

    Quindi eseguiamo l’iterazione con do print(x); while (next(x)); do print(x); while (next(x)); .

    Ora alcuni commenti sulla complessità, m_i > 1 dal presupposto che m_i > 1 per tutti i :

    • Questo algoritmo richiede O(n) spazio. Si noti che la costruzione esplicita del prodotto cartesiano richiede O(m_0 m_1 m_2 ... m_{n-1}) >= O(2^n) spazio. Quindi questo è esponenzialmente migliore sullo spazio rispetto a qualsiasi algoritmo che richiede che tutte le tuple vengano memorizzate simultaneamente in memoria.
    • La funzione next prende il tempo O(1) ammortizzato (per un argomento serie geometrico).
    • La funzione di print richiede O(n) tempo.
    • Quindi, nel complesso, l’algoritmo ha complessità temporale O(n|M|) e complessità spaziale O(n) (senza contare il costo di memorizzazione degli items ).

    Una cosa interessante da notare è che se la print viene sostituita con una funzione che controlla in media solo le coordinate O(1) per tupla piuttosto che tutte, allora la complessità temporale cade su O(|M|) , cioè diventa lineare tempo rispetto alle dimensioni del prodotto cartesiano. In altre parole, evitando la copia della tupla ogni iterazione può essere significativa in alcune situazioni.

    Questa versione non supporta iteratori o intervalli, ma è un’implementazione diretta semplice che utilizza l’operatore di moltiplicazione per rappresentare il prodotto cartesiano e un lambda per eseguire l’azione.

    L’interfaccia è stata progettata con la particolare funzionalità di cui avevo bisogno. Avevo bisogno della flessibilità per scegliere i vettori su cui applicare il prodotto cartesiano in un modo che non oscurasse il codice.

     int main() { vector< vector > v{ { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } }; (Cartesian(v[0]) * v[1] * v[2]).ForEach( [](long p_Depth, long *p_LongList) { std::cout << p_LongList[0] << " " << p_LongList[1] << " " << p_LongList[2] << std::endl; } ); } 

    L'implementazione utilizza la ricorsione sulla struttura della class per implementare i loop incorporati per ogni vettore. L'algoritmo funziona direttamente sui vettori di input, non richiedendo grandi array temporanei. È semplice da capire e fare il debug.

    L'uso di std :: function p_Action invece di void p_Action (long p_Depth, T * p_ParamList) per il parametro lambda mi permetterebbe di acquisire variabili locali, se volessi. Nella chiamata sopra, io no.

    Ma lo sapevi, vero? "function" è una class template che accetta il parametro type di una funzione e la rende richiamabile.

     #include  #include  #include  #include  using namespace std; template  class Cartesian { private: vector &m_Vector; Cartesian *m_Cartesian; public: Cartesian(vector &p_Vector, Cartesian *p_Cartesian=NULL) : m_Vector(p_Vector), m_Cartesian(p_Cartesian) {}; virtual ~Cartesian() {}; Cartesian *Clone() { return new Cartesian(m_Vector, m_Cartesian ? m_Cartesian->Clone() : NULL); }; Cartesian &operator *=(vector &p_Vector) { if (m_Cartesian) (*m_Cartesian) *= p_Vector; else m_Cartesian = new Cartesian(p_Vector); return *this; }; Cartesian operator *(vector &p_Vector) { return (*Clone()) *= p_Vector; }; long Depth() { return m_Cartesian ? 1 + m_Cartesian->Depth() : 1; }; void ForEach(function p_Action) { Loop(0, new T[Depth()], p_Action); }; private: void Loop(long p_Depth, T *p_ParamList, function p_Action) { for (T &element : m_Vector) { p_ParamList[p_Depth] = element; if (m_Cartesian) m_Cartesian->Loop(p_Depth + 1, p_ParamList, p_Action); else p_Action(Depth(), p_ParamList); } }; };