如何创建矢量矢量的笛卡尔乘积？ [英] How can I create cartesian product of vector of vectors?

问题描述

我有一个向量向量说 vector< vector< int> >

I've a vector of vectors say vector<vector<int> > items of different sizes like as follows

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

我想根据这些向量如

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

？我查了几个链接，我也列出了他们在这篇文章的结尾，但我不能解释，因为我不熟悉的语言。可能有一些身体帮助我这个。

How can I do that ? I've looked up several links and I've also listed them at the end of this post but I'm not able to interpret that as I'm not that familiar with the language. Could some body help me with this.

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

int main()
{
    vector<vector<int> > items;
    int k = 0;

    for ( int i = 0; i < 5; i++ ) {
        items.push_back ( vector<int>() );

        for ( int j = 0; j < 5; j++ )
            items[i].push_back ( k++ );
    }

    cartesian ( items ); // I want some function here to do this.
}

这个程序有相等的长度向量，我把它放在这里，了解我的数据结构。这将是非常有益的，即使有人使用其他链接的其他答案，并与此集成，以获得结果。非常感谢

This program has equal length vectors and I put this so that it will be easier to understand my data structure. It will be very helpful even if somebody uses others answers from other links and integrate with this to get the result. Thank you very much

几个链接我看着
一个
两个
程序从：程序

推荐答案

首先，我将向你展示一个递归版本。

First, I'll show you a recursive version.

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

现在，我将向您展示递归我无耻地从@John窃取的迭代版本：

Now, I'll show you the recursive iterative version that I shamelessly stole from @John :

程序的其余部分几乎相同，只显示 cart_product function。

The rest of the program is pretty much the same, only showing the cart_product function.

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

这篇关于如何创建矢量矢量的笛卡尔乘积？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！