StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First, I'll show you a recursive version. </p> <pre><code>// Cartesion product of vector of vectors #include <vector> #include <iostream> #include <iterator> // Types to hold vector-of-ints (Vi) and vector-of-vector-of-ints (Vvi) typedef std::vector<int> Vi; typedef std::vector<Vi> 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<int>(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"; } </code></pre> <p>Now, I'll show you the <strike>recursive</strike> iterative version that I shamelessly stole from @John :</p> <p>The rest of the program is pretty much the same, only showing the <code>cart_product</code> function.</p> <pre><code>// 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; } } } } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload