如何创建向量向量的笛卡尔积?

2021-12-21 00:00:00 combinations cartesian-product vector c++

我有一个向量向量说 vector;>不同大小的项目如下

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

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

I want to create combinations in terms of Cartesian product of these vectors like

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

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

Couple of links I looked at one Two Program from : program

推荐答案

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

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 << "(
";
  for(Vvi::const_iterator it = vvi.begin();
      it != vvi.end();
      it++) {
      os << "  " << *it << "
";
  }
  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 << "
";

  Vvi output;
  Vi outputTemp;
  cart_product(output, outputTemp, input.begin(), input.end());
  std::cout << output << "
";
}

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

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

程序的其余部分几乎相同，仅显示cart_product 函数.

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

相关文章