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

我有一个向量的矢量说
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.
}
这个程序有相同的长度向量，我把它放在这里，以便更容易理解我的数据结构。即使有人使用其他链接中的其他答案并与此集成以获得结果，这将非常有用。非常感谢你 我看了几个链接 一 二 计划来自：计划     
2019-10-20 10 条评论
分享

没有找到相关结果

    已邀请:

    摊揉售

    首先，我将向您展示一个递归版本。 
    // 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;
            }
        }
    }
}
        
    2019-10-20 0 0
    分享

    膝垫富顷

    这是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
        
    2019-10-20 0 0
    分享

    师埠女

    更短的代码： 
    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;
}
        
    2019-10-20 0 0
    分享

    肉簧咸缮

    这是我的解决方案。也是迭代的，但比上面的短一点...... 
    void xp(const vector<vector<int>*>& vecs, vector<vector<int>*> *result) {
  vector<vector<int>*>* rslts;
  for (int ii = 0; ii < vecs.size(); ++ii) {
    const vector<int>& vec = *vecs[ii];
    if (ii == 0) {
      // vecs=[[1,2],...] ==> rslts=[[1],[2]]
      rslts = new vector<vector<int>*>;
      for (int jj = 0; jj < vec.size(); ++jj) {
        vector<int>* v = new vector<int>;
        v->push_back(vec[jj]);
        rslts->push_back(v);
      }
    } else {
      // vecs=[[1,2],[3,4],...] ==> rslts=[[1,3],[1,4],[2,3],[2,4]]
      vector<vector<int>*>* tmp = new vector<vector<int>*>;
      for (int jj = 0; jj < vec.size(); ++jj) {  // vec[jj]=3 (first iter jj=0)
        for (vector<vector<int>*>::const_iterator it = rslts->begin();
             it != rslts->end(); ++it) {
          vector<int>* v = new vector<int>(**it);       // v=[1]
          v->push_back(vec[jj]);                        // v=[1,3]
          tmp->push_back(v);                            // tmp=[[1,3]]
        }
      }
      for (int kk = 0; kk < rslts->size(); ++kk) {
        delete (*rslts)[kk];
      }
      delete rslts;
      rslts = tmp;
    }
  }
  result->insert(result->end(), rslts->begin(), rslts->end());
  delete rslts;
}
    我从我写的haskell版本中得到了一些痛苦： 
    xp :: [[a]] -> [[a]]
xp [] = []
xp [l] = map (:[]) l
xp (h:t) = foldr (x acc -> foldr (l acc -> (x:l):acc) acc (xp t)) [] h
        
    2019-10-20 0 0
    分享

    柑恫祟

    好像你想要一个
    vector
    的迭代器迭代你的个人
    vector<int>
    s。 在开始时启动所有迭代器。通过迭代器拉出每个向量的元素来构造您的第一个产品向量。 增加最右边的一个，然后重复。 当你到达最后，将那个重置为开头并递增倒数第二个。您可以通过将它从迭代器向量中的相邻元素中拉出来获得“倒数第二个”迭代器。 继续循环，直到最后和倒数第二个迭代器都结束。然后，重置它们，增加倒数第三个迭代器。一般来说，这可以级联。 它就像一个里程表，但每个不同的数字都在不同的基础上。     
    2019-10-20 0 0
    分享

    吠强祷豪硅

    由于我需要相同的功能，我实现了一个迭代器，它根据需要动态计算笛卡尔积，并迭代它。 它可以如下使用。 
    #include <forward_list>
#include <iostream>
#include <vector>
#include "cartesian.hpp"

int main()
{
    // Works with a vector of vectors
    std::vector<std::vector<int>> test{{1,2,3}, {4,5,6}, {8,9}};
    CartesianProduct<decltype(test)> cp(test);
    for(auto const& val: cp) {
        std::cout << val.at(0) << ", " << val.at(1) << ", " << val.at(2) << "n";
    }

    // Also works with something much less, like a forward_list of forward_lists
    std::forward_list<std::forward_list<std::string>> foo{{"boo", "far", "zab"}, {"zoo", "moo"}, {"yohoo", "bohoo", "whoot", "noo"}};
    CartesianProduct<decltype(foo)> bar(foo);
    for(auto const& val: bar) {
        std::cout << val.at(0) << ", " << val.at(1) << ", " << val.at(2) << "n";
    }
}
    文件cartesian.hpp看起来像这样。 
    #include <cassert>

#include <limits>
#include <stdexcept>
#include <vector>

#include <boost/iterator/iterator_facade.hpp>

//! Class iterating over the Cartesian product of a forward iterable container of forward iterable containers
template<typename T>
class CartesianProductIterator : public boost::iterator_facade<CartesianProductIterator<T>, std::vector<typename T::value_type::value_type> const, boost::forward_traversal_tag>
{
    public:
        //! Delete default constructor
        CartesianProductIterator() = delete;

        //! Constructor setting the underlying iterator and position
        /*!
         * param[in] structure The underlying structure
         * param[in] pos The position the iterator should be initialized to.  std::numeric_limits<std::size_t>::max()stands for the end, the position after the last element.
         */
        explicit CartesianProductIterator(T const& structure, std::size_t pos);

    private:
        //! Give types more descriptive names
        // {
        typedef T OuterContainer;
        typedef typename T::value_type Container;
        typedef typename T::value_type::value_type Content;
        // }

        //! Grant access to boost::iterator_facade
        friend class boost::iterator_core_access;

        //! Increment iterator
        void increment();

        //! Check for equality
        bool equal(CartesianProductIterator<T> const& other) const;

        //! Dereference iterator
        std::vector<Content> const& dereference() const;

        //! The part we are iterating over
        OuterContainer const& structure_;

        //! The position in the Cartesian product
        /*!
         * For each element of structure_, give the position in it.
         * The empty vector represents the end position.
         * Note that this vector has a size equal to structure->size(), or is empty.
         */
        std::vector<typename Container::const_iterator> position_;

        //! The position just indexed by an integer
        std::size_t absolutePosition_ = 0;

        //! The begin iterators, saved for convenience and performance
        std::vector<typename Container::const_iterator> cbegins_;

        //! The end iterators, saved for convenience and performance
        std::vector<typename Container::const_iterator> cends_;

        //! Used for returning references
        /*!
         * We initialize with one empty element, so that we only need to add more elements in increment().
         */
        mutable std::vector<std::vector<Content>> result_{std::vector<Content>()};

        //! The size of the instance of OuterContainer
        std::size_t size_ = 0;
};

template<typename T>
CartesianProductIterator<T>::CartesianProductIterator(OuterContainer const& structure, std::size_t pos) : structure_(structure)
{
    for(auto & entry: structure_) {
        cbegins_.push_back(entry.cbegin());
        cends_.push_back(entry.cend());
        ++size_;
    }

    if(pos == std::numeric_limits<std::size_t>::max() || size_ == 0) {
        absolutePosition_ = std::numeric_limits<std::size_t>::max();
        return;
    }

    // Initialize with all cbegin() position
    position_.reserve(size_);
    for(std::size_t i = 0; i != size_; ++i) {
        position_.push_back(cbegins_[i]);
        if(cbegins_[i] == cends_[i]) {
            // Empty member, so Cartesian product is empty
            absolutePosition_ = std::numeric_limits<std::size_t>::max();
            return;
        }
    }

    // Increment to wanted position
    for(std::size_t i = 0; i < pos; ++i) {
        increment();
    }
}

template<typename T>
void CartesianProductIterator<T>::increment()
{
    if(absolutePosition_ == std::numeric_limits<std::size_t>::max()) {
        return;
    }

    std::size_t pos = size_ - 1;

    // Descend as far as necessary
    while(++(position_[pos]) == cends_[pos] && pos != 0) {
        --pos;
    }
    if(position_[pos] == cends_[pos]) {
        assert(pos == 0);
        absolutePosition_ = std::numeric_limits<std::size_t>::max();
        return;
    }
    // Set all to begin behind pos
    for(++pos; pos != size_; ++pos) {
        position_[pos] = cbegins_[pos];
    }
    ++absolutePosition_;
    result_.emplace_back();
}

template<typename T>
std::vector<typename T::value_type::value_type> const& CartesianProductIterator<T>::dereference() const
{
    if(absolutePosition_ == std::numeric_limits<std::size_t>::max()) {
        throw new std::out_of_range("Out of bound dereference in CartesianProductIteratorn");
    }
    auto & result = result_[absolutePosition_];
    if(result.empty()) {
        result.reserve(size_);
        for(auto & iterator: position_) {
            result.push_back(*iterator);
        }
    }

    return result;
}

template<typename T>
bool CartesianProductIterator<T>::equal(CartesianProductIterator<T> const& other) const
{
    return absolutePosition_ == other.absolutePosition_ && structure_ == other.structure_;
}

//! Class that turns a forward iterable container of forward iterable containers into a forward iterable container which iterates over the Cartesian product of the forward iterable containers
template<typename T>
class CartesianProduct
{
    public:
        //! Constructor from type T
        explicit CartesianProduct(T const& t) : t_(t) {}

        //! Iterator to beginning of Cartesian product
        CartesianProductIterator<T> begin() const { return CartesianProductIterator<T>(t_, 0); }

        //! Iterator behind the last element of the Cartesian product
        CartesianProductIterator<T> end() const { return CartesianProductIterator<T>(t_, std::numeric_limits<std::size_t>::max()); }

    private:
        T const& t_;
};
    如果有人发表评论如何让它变得更快或更好，我会非常感激他们。     
    2019-10-20 0 0
    分享

    绵扇寸访

    我只是被迫为我正在进行的项目实现这个，我想出了下面的代码。它可以卡在标题中，它的使用非常简单但它返回了你可以从矢量矢量得到的所有组合。它返回的数组只保存整数。这是一个有意识的决定，因为我只想要指数。通过这种方式，我可以索引每个向量的向量，然后执行我/任何人需要的计算...最好避免让CartesianProduct保持“东西”本身，这是一个基于计算而不是数据结构的数学概念。我对c ++很新，但是在解密算法中进行了相当彻底的测试。有一些轻微的递归，但总的来说这是一个简单的计数概念的简单实现。 
    // Use of the CartesianProduct class is as follows. Give it the number
// of rows and the sizes of each of the rows. It will output all of the 
// permutations of these numbers in their respective rows.
// 1. call cp.permutation() // need to check all 0s.
// 2. while cp.HasNext() // it knows the exit condition form its inputs.
// 3.   cp.Increment() // Make the next permutation
// 4.   cp.permutation() // get the next permutation

class CartesianProduct{
  public:
  CartesianProduct(int num_rows, vector<int> sizes_of_rows){
    permutation_ = new int[num_rows];
    num_rows_ = num_rows;
    ZeroOutPermutation();
    sizes_of_rows_ = sizes_of_rows;
    num_max_permutations_ = 1;
    for (int i = 0; i < num_rows; ++i){
      num_max_permutations_ *= sizes_of_rows_[i]; 
    }
  }

  ~CartesianProduct(){
    delete permutation_;
  }

  bool HasNext(){
    if(num_permutations_processed_ != num_max_permutations_) {
      return true;
    } else {
      return false;
    }
  }

 void Increment(){
    int row_to_increment = 0;
    ++num_permutations_processed_;
    IncrementAndTest(row_to_increment);
  }

  int* permutation(){
    return permutation_;
  }

  int num_permutations_processed(){
    return num_permutations_processed_;
  }
  void PrintPermutation(){
    cout << "( ";
    for (int i = 0; i < num_rows_; ++i){
      cout << permutation_[i] << ", ";
    }
    cout << " )" << endl;
  }

private:
  int num_permutations_processed_;
  int *permutation_;
  int num_rows_;
  int num_max_permutations_;
  vector<int> sizes_of_rows_;

  // Because CartesianProduct is called first initially with it's values
  // of 0 and because those values are valid and important output
  // of the CartesianProduct we increment the number of permutations
  // processed here when  we populate the permutation_ array with 0s.
  void ZeroOutPermutation(){
    for (int i = 0; i < num_rows_; ++i){
      permutation_[i] = 0;
    }

    num_permutations_processed_ = 1;
  }

  void IncrementAndTest(int row_to_increment){
    permutation_[row_to_increment] += 1;
    int max_index_of_row = sizes_of_rows_[row_to_increment] - 1;
    if (permutation_[row_to_increment] > max_index_of_row){
      permutation_[row_to_increment] = 0;
      IncrementAndTest(row_to_increment + 1);
    }
  }
};
        
    2019-10-20 0 0
    分享

    苦诫 

    #include <iostream>
#include <vector>

void cartesian (std::vector<std::vector<int>> const& items) {
  auto n = items.size();
  auto next = [&](std::vector<int> & x) {
      for ( int i = 0; i < n; ++ i ) 
        if ( ++x[i] == items[i].size() ) x[i] = 0; 
        else return true;
      return false;
  };
  auto print = [&](std::vector<int> const& x) {
    for ( int i = 0; i < n; ++ i ) 
      std::cout << items[i][x[i]] << ",";
    std::cout << "b n";
  };
  std::vector<int> x(n);
  do print(x); while (next(x)); // Shazam!
}

int main () {
  std::vector<std::vector<int>> 
    items { { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } };
  cartesian(items);
  return 0;
}
    这背后的想法如下。 让
    n := items.size()
    。 让
    m_i := items[i].size()
    ，对于
    {0,1,...,n-1}
    中的所有
    i
    。 让
    M := {0,1,...,m_0-1} x {0,1,...,m_1-1} x ... x {0,1,...,m_{n-1}-1}
    。 我们首先解决迭代
    M
    的简单问题。这是由
    next
    lambda完成的。该算法只是“携带”常规等级学习者用于添加1，尽管具有混合基数系统。 我们使用它来解决更普遍的问题，通过公式
    items[i][x[i]]
    将
    M
    中的元组
    x
    转换为所需的元组之一，用于
    {0,1,...,n-1}
    中的所有
    i
    。我们在
    print
    lambda中进行这种转换。 然后我们用
    do print(x); while (next(x));
    执行迭代。 现在有一些关于复杂性的评论，假设所有
    m_i > 1
    为
    m_i > 1
    ： 该算法需要
    O(n)
    空间。请注意，笛卡尔积的显式构造需要
    O(m_0 m_1 m_2 ... m_{n-1}) >= O(2^n)
    空间。因此，这比任何需要将所有元组同时存储在内存中的算法在空间上指数级更好。 
    next
    函数需要摊销
    O(1)
    时间（通过几何级数参数）。 
    print
    功能需要
    O(n)
    时间。 因此，该算法总共具有时间复杂度
    O(n|M|)
    和空间复杂度
    O(n)
    （不计算存储成本
    items
    ）。 一个值得注意的有趣的事情是，如果将
    print
    替换为平均每个元组仅检测
    O(1)
    坐标而不是全部检测的函数，则时间复杂度降至
    O(|M|)
    ，也就是说，它变为相对于大小的线性时间。笛卡尔积。换句话说，在某些情况下，避免每次迭代的元组副本可能是有意义的。     
    2019-10-20 0 0
    分享

    扫窟

    此版本不支持迭代器或范围，但它是一个简单的直接实现，它使用乘法运算符表示笛卡尔积，并使用lambda来执行操作。 界面设计具有我需要的特定功能。我需要灵活地选择向量来应用笛卡尔积，其方式不会掩盖代码。 
    int main()
{
    vector< vector<long> > v{ { 1, 2, 3 }, { 4, 5 }, { 6, 7, 8 } };
    (Cartesian<long>(v[0]) * v[1] * v[2]).ForEach(
        [](long p_Depth, long *p_LongList)
        {
            std::cout << p_LongList[0] << " " << p_LongList[1] << " " << p_LongList[2] << std::endl;
        }
    );
}
    该实现使用递归类结构来实现每个向量上的嵌入式for循环。该算法直接在输入向量上工作，不需要大的临时数组。理解和调试很简单。 如果我愿意，使用std :: function p_Action而不是void p_Action（long p_Depth，T * p_ParamList）作为lambda参数将允许我捕获局部变量。在上面的电话中，我没有。 但是你知道，不是吗。 “function”是一个模板类，它接受函数的类型参数并使其可调用。 
    #include <vector>
#include <iostream>
#include <functional>
#include <string>
using namespace std;

template <class T>
class Cartesian
{
private:
    vector<T> &m_Vector;
    Cartesian<T> *m_Cartesian;
public:
    Cartesian(vector<T> &p_Vector, Cartesian<T> *p_Cartesian=NULL)
        : m_Vector(p_Vector), m_Cartesian(p_Cartesian)
    {};
    virtual ~Cartesian() {};
    Cartesian<T> *Clone()
    {
        return new Cartesian<T>(m_Vector, m_Cartesian ? m_Cartesian->Clone() : NULL);
    };
    Cartesian<T> &operator *=(vector<T> &p_Vector)
    {
        if (m_Cartesian)
            (*m_Cartesian) *= p_Vector;
        else
            m_Cartesian = new Cartesian(p_Vector);
        return *this;
    };
    Cartesian<T> operator *(vector<T> &p_Vector)
    {
        return (*Clone()) *= p_Vector;
    };
    long Depth()
    {
        return m_Cartesian ? 1 + m_Cartesian->Depth() : 1;
    };
    void ForEach(function<void (long p_Depth, T *p_ParamList)> p_Action)
    {
        Loop(0, new T[Depth()], p_Action);
    };
private:
    void Loop(long p_Depth, T *p_ParamList, function<void (long p_Depth, T *p_ParamList)> p_Action)
    {
        for (T &element : m_Vector)
        {
            p_ParamList[p_Depth] = element;
            if (m_Cartesian)
                m_Cartesian->Loop(p_Depth + 1, p_ParamList, p_Action);
            else
                p_Action(Depth(), p_ParamList);
        }
    };
};
        
    2019-10-20 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.037171840667725