如何创建矢量矢量的笛卡尔积？

Question

我有一个矢量说vector<vector<int> > items不同大小的矢量,如下所示

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

我想根据这些向量的笛卡尔积来创建组合

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

我怎样才能做到这一点 ？我查了几个链接,我也在这篇文章的末尾列出了它们,但我无法解释它,因为我不熟悉这种语言.有些人可以帮助我.

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

这个程序有相同的长度向量,我把它放在这里,以便更容易理解我的数据结构.即使有人使用其他链接中的其他答案并与此集成以获得结果,这将非常有用.非常感谢你

几个链接我看了 一个 两个 程序:程序

Answer 1

首先,我将向您展示一个递归版本.

// 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无耻地偷走的递归迭代版本:

程序的其余部分几乎相同,仅显示cart_product功能.

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

Answer 2

这是C++ 11中的解决方案.

可以使用模运算雄辩地完成可变大小数组的索引.

输出中的总行数是输入向量大小的乘积.那是:

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

因此,主回路具有n作为迭代变量,从0到N-1.原则上,每个值n编码足够的信息以提取v该迭代的每个索引.这是使用重复的模运算在子循环中完成的:

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

输出:

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

Answer 3

更短的代码:

vector<vector<int>> cart_product (const vector<vector<int>>& v) {
    vector<vector<int>> s = {{}};
    for (const auto& u : v) {
        vector<vector<int>> 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;
}