¿Cómo puedo crear el producto cartesiano de un vector de vectores?
Tengo un vector de vectores, digamos vector<vector<int>>de diferentes tamaños, de la siguiente manera:
vector<vector<int>> items = {
{ 1, 2, 3 },
{ 4, 5 },
{ 6, 7, 8 }
};
Quiero crear combinaciones en términos del producto cartesiano de estos vectores como
1,4,6
1,4,7
1,4,8
1,5,6
// ...
3,5,7
3,5,8
¿Cómo puedo hacer eso?
Primero, les mostraré una versión recursiva.
typedef std::vector<int> Vi;
typedef std::vector<Vi> Vvi;
// 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
}
}
Vea el código completo en Compiler Explorer .
Ahora, les mostraré la versión iterativa recursiva que le robé descaradamente a @John:
// Seems like you'd want a vector of iterators
// which iterate over your individual vector<int>s.
struct Digits {
Vi::const_iterator begin;
Vi::const_iterator end;
Vi::const_iterator me;
};
typedef std::vector<Digits> 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;
}
}
}
}
Aquí hay una solución en C++11.
La indexación de matrices de tamaño variable se puede realizar de forma elocuente con aritmética modular.
El número total de líneas en la salida es el producto de los tamaños de los vectores de entrada. Eso es:
N = v[0].size() * v[1].size() * v[2].size()
Por lo tanto, el bucle principal tiene ncomo variable de iteración, desde 0hasta N-1. En principio, cada valor de ncodifica suficiente información para extraer cada uno de los índices de vpara esa iteración. Esto se hace en un subbucle usando aritmética modular repetida:
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
void cartesian( vector<vector<int> >& v ) {
auto product = []( long long a, vector<int>& b ) { return a*b.size(); };
const long long N = accumulate( v.begin(), v.end(), 1LL, product );
vector<int> u(v.size());
for( long long n=0 ; n<N ; ++n ) {
lldiv_t q { n, 0 };
for( long long i=v.size()-1 ; 0<=i ; --i ) {
q = div( q.quot, v[i].size() );
u[i] = v[i][q.rem];
}
// Do what you want here with u.
for( int x : u ) cout << x << ' ';
cout << '\n';
}
}
int main() {
vector<vector<int> > v { { 1, 2, 3 },
{ 4, 5 },
{ 6, 7, 8 } };
cartesian(v);
return 0;
}
Producción:
1 4 6
1 4 7
1 4 8
...
3 5 8
Código más corto:
vector<vector<int>> cart_product (const vector<vector<int>>& in) {
// note: this creates a vector containing one empty vector
vector<vector<int>> results = {{}};
for (const auto& new_values : in) {
// helper vector so that we don't modify results while iterating
vector<vector<int>> next_results;
for (const auto& result : results) {
for (const auto value : new_values) {
next_results.push_back(result);
next_results.back().push_back(value);
}
}
results = move(next_results);
}
return result;
}
