Como posso criar um produto cartesiano de vetor de vetores?

Eu tenho um vetor de vetores dizer vector<vector > items de tamanhos diferentes, como segue

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

Eu quero criar combinações em termos de produto cartesiano desses vetores como

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

Como eu posso fazer isso ? Eu pesquisei vários links e também os listei no final deste post, mas não consigo interpretar isso, já que não estou familiarizado com o idioma. Algum corpo poderia me ajudar com isso?

 #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. } 

Este programa tem vetores de comprimento igual e eu coloco isso para que seja mais fácil entender minha estrutura de dados. Será muito útil mesmo que alguém use outras respostas de outros links e se integre com isso para obter o resultado. Muito obrigado

Par de links Eu olhei para um programa de dois de: programa

Primeiro, vou mostrar uma versão recursiva.

 // 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"; } 

Agora, mostrarei a versão iterativa recursiva que eu descaradamente roubei do @John:

O resto do programa é praticamente o mesmo, mostrando apenas a function 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; } } } } 

Aqui está uma solução em C ++ 11.

A indexação dos arrays de tamanho variável pode ser feita de forma eloquente com aritmética modular.

O número total de linhas na saída é o produto dos tamanhos dos vetores de input. Isso é:

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

Portanto, o loop principal tem n como a variável de iteração, de 0 a N-1 . Em princípio, cada valor de n codifica informação suficiente para extrair cada um dos índices de v para aquela iteração. Isso é feito em um subloop usando aritmética modular repetida:

 #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; } 

Saída:

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

Código mais curto:

 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; } 

Aqui está minha solução. Também iterativo, mas um pouco mais curto que o anterior …

 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; } 

Eu deduzi com alguma dor de uma versão haskell que escrevi:

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

Parece que você deseja um vector de iteradores que se repetem no seu vector individual vector s.

Inicie todos os iteradores no começo. Construa seu primeiro vetor de produto puxando o elemento de cada vetor através do iterador.

Incremente o mais à direita e repita.

Quando chegar ao fim, redefina-o para o começo e incremente o penúltimo. Você pode obter o iterador “next-to-last”, puxando-o para fora do elemento vizinho em seu vetor de iteradores.

Continue a percorrer até que os últimos e os últimos iteradores estejam no final. Em seguida, redefina ambos, incrementar o terceiro do último iterador. Em geral, isso pode ser em cascata.

É como um odômetro, mas com cada dígito diferente em uma base diferente.

Como eu precisava da mesma funcionalidade, implementei um iterador que calcula o produto cartesiano rapidamente, conforme necessário, e faz a iteração sobre ele.

Pode ser usado da seguinte maneira.

 #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"; } } 

O arquivo cartesian.hpp se parece com isso.

 #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 alguém tiver comentários sobre como torná-lo mais rápido ou melhor, agradeço muito a eles.

Eu fui forçado a implementar isso para um projeto em que estava trabalhando e eu criei o código abaixo. Ele pode ser preso em um header e seu uso é muito simples, mas retorna todas as combinações que você pode obter de um vetor de vetores. A matriz que retorna apenas contém números inteiros. Esta foi uma decisão consciente porque eu só queria os índices. Desta forma, eu poderia indexar cada vetor do vetor e então executar os cálculos que eu / qualquer um precisaria … melhor para evitar que o CartesianProduct mantenha o “material” em si, é um conceito matemático baseado na contagem e não na estrutura de dados. Eu sou bastante novo para c + +, mas isso foi testado em um algoritmo de descriptografia muito bem. Há alguma recursion de luz, mas no geral esta é uma implementação simples de um conceito de contagem simples.

 // 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; } 

A ideia por trás disso é a seguinte.

Vamos n := items.size() .
Deixe m_i := items[i].size() , para todos i em {0,1,...,n-1} .
Seja M := {0,1,...,m_0-1} x {0,1,...,m_1-1} x ... x {0,1,...,m_{n-1}-1} .

Primeiro resolvemos o problema mais simples de iterar através de M Isso é realizado pelo next lambda. O algoritmo é simplesmente o tipo de escolaridade de rotina que “carrega” para adicionar 1, embora com um sistema de números mistos.

Usamos isso para resolver o problema mais geral transformando uma tupla x em M em uma das tuplas desejadas através dos items[i][x[i]] fórmula items[i][x[i]] para todo o i em {0,1,...,n-1} . Nós realizamos esta transformação no lambda print .

Em seguida, executamos a iteração com do print(x); while (next(x)); do print(x); while (next(x)); .

Agora, alguns comentários sobre a complexidade, sob o pressuposto de que m_i > 1 para todos i :

  • Este algoritmo requer O(n) espaço. Observe que a construção explícita do produto cartesiano toma o espaço O(m_0 m_1 m_2 ... m_{n-1}) >= O(2^n) . Portanto, isso é exponencialmente melhor no espaço do que qualquer algoritmo que requer que todas as tuplas sejam armazenadas simultaneamente na memory.
  • A next function toma o tempo O(1) amortizado (por um argumento de série geométrica).
  • A function de print leva o tempo O(n) .
  • Assim, ao todo, o algoritmo tem complexidade de tempo O(n|M|) e complexidade de espaço O(n) (sem contar o custo de armazenar items ).

Uma coisa interessante a notar é que, se a print for substituída por uma function que inspecione, em média, apenas O(1) coordenadas por tupla, em vez de todas elas, então a complexidade de tempo cairá para O(|M|) , tempo em relação ao tamanho do produto cartesiano. Em outras palavras, evitar a cópia da tupla a cada iteração pode ser significativo em algumas situações.

Essa versão não suporta iteradores ou intervalos, mas é uma implementação direta simples que usa o operador de multiplicação para representar o produto cartesiano e um lambda para executar a ação.

A interface é projetada com a funcionalidade específica que eu precisava. Eu precisava da flexibilidade de escolher vetores sobre os quais aplicar o produto cartesiano de uma maneira que não obscurecesse o código.

 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; } ); } 

A implementação usa a recursion da estrutura de classs para implementar os loops forçados incorporados em cada vetor. O algoritmo funciona diretamente nos vetores de input, não exigindo grandes matrizes temporárias. É simples de entender e depurar.

O uso de std :: function p_Action em vez de void p_Action (long p_Depth, T * p_ParamList) para o parâmetro lambda me permitiria capturar variables ​​locais, se eu quisesse. Na chamada acima, eu não faço.

Mas você sabia disso, não sabia? "function" é uma class de template que pega o parâmetro type de uma function e a torna chamavel.

 #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); } }; };