Comment créer un produit cartésien de vecteur de vecteurs?

Voici une solution en C++11.

l'indexation des tableaux de dimensions variables peut être effectuée avec éloquence à l'aide de l'arithmétique modulaire.

le nombre total de lignes dans la sortie est le produit des tailles des vecteurs d'entrée. C'est-à-dire:

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

donc la boucle principale a n comme variable d'itération, de 0 à N-1 . En principe, chaque valeur de n code assez information pour extraire chacun des indices de v pour cette itération. Cela se fait en sous-boucle en utilisant l'arithmétique modulaire répétée:

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

sortie:

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

plus Court code:

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

voici ma solution. Aussi itératif, mais un peu plus court que le précédent...

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

Je l'ai dérivé avec un peu de douleur d'une version haskell j'ai écrit:

xp :: [[a]] -> [[a]]
xp [] = []
xp [l] = map (:[]) l
xp (h:t) = foldr (\x acc -> foldr (\l acc -> (x:l):acc) acc (xp t)) [] h

semble comme vous voudriez un vector d'itérateurs qui itèrent au-dessus de votre individu vector<int> S.

Démarrer tous les itérateurs au début. Construire votre premier produit vectoriel en tirant sur l'élément de chaque vecteur par l'itérateur.

incrémentez le plus à droite, et répétez.

quand vous atteignez la fin, réinitialisez celle-ci au début et incrémentez la suivante-dernière. Vous pouvez obtenir le "avant-dernier" itérateur en le tirant hors de l'voisins de l'élément dans le vecteur d'itérateurs.

continuer le cyclage jusqu'à les deux les derniers et les derniers itérateurs sont à la fin. Puis, réinitialisez les deux, incrémentez le troisième-du-dernier itérateur. En général, cela peut être en cascade.

c'est comme un odomètre, mais avec chaque chiffre différent étant dans une base différente.

comme j'avais besoin de la même fonctionnalité, j'ai implémenté un itérateur qui calcule le produit cartésien à la volée, selon les besoins, et itère par-dessus.

Il peut être utilisé comme suit.

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

le fichier cartésien.php ressemble à ceci.

#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 CartesianProductIterator\n");
    }
    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_;
};

si quelqu'un a des commentaires sur la façon de le rendre plus rapide ou mieux, je les apprécierais beaucoup.

j'ai juste été forcé de mettre en œuvre ceci pour un projet sur lequel je travaillais et je suis venu avec le code ci-dessous. Il peut être coincé dans un en-tête et son utilisation est très simple, mais il renvoie toutes les combinaisons que vous pouvez obtenir à partir d'un vecteur de vecteurs. Le tableau qu'il retourne ne contient que des entiers. C'était une décision consciente parce que je voulais juste les indices. De cette façon, je pourrais indexer dans chacun du vecteur du vecteur et puis effectuer les calculs que je/n'importe qui aurait besoin... le mieux pour éviter laisser CartesianProduct tenir le "truc" lui-même, c'est un concept mathématique basé sur le comptage et non sur une structure de données. Je suis assez nouveau en c++ mais cela a été testé dans un algorithme de décryptage assez minutieusement. Il y a une légère récursion, mais dans l'ensemble il s'agit d'une simple mise en œuvre d'un concept de comptage simple.

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

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

l'idée derrière ceci est la suivante.

Let n := items.size() .

Soit m_i := items[i].size() , pour tous i dans {0,1,...,n-1} .

Soit M := {0,1,...,m_0-1} x {0,1,...,m_1-1} x ... x {0,1,...,m_{n-1}-1} .

nous résolvons d'abord le problème plus simple de l'itération par M . Ceci est accompli par le next lambda. L'algorithme est tout simplement le "porteur" de l'école primaire de routine utilisent pour ajouter 1, mais avec un mélange système de numéros radix.

nous l'utilisons pour résoudre le problème plus général en transformant un tuple x dans M en un des tuples désirés via la formule items[i][x[i]] pour tous i dans {0,1,...,n-1} . Nous réalisons cette transformation dans la lambda print .

nous effectuons ensuite l'itération avec do print(x); while (next(x)); .

maintenant quelques commentaires sur la complexité, sous l'hypothèse que m_i > 1 pour tous les i :

• cet algorithme nécessite O(n) espace. Notez que la construction explicite du produit cartésien prend O(m_0 m_1 m_2 ... m_{n-1}) >= O(2^n) espace. Donc, c'est exponentiellement mieux sur l'espace que n'importe quel algorithme qui exige que tous les tuples soient stockés simultanément en mémoire.
• la fonction next prend le temps amorti O(1) (par un argument de série géométrique).
• le print fonction prend O(n) temps.
• donc, tout à fait, l'algorithme a la complexité de temps O(n|M|) et la complexité de l'espace O(n) (sans compter le coût de stockage de items ).

une chose intéressante à noter est que si print est remplacé par une fonction qui inspecte en moyenne seulement O(1) coordonnées par tuple plutôt que tous les tuples, alors la complexité de temps tombe à O(|M|) , c'est-à-dire, il devient, le temps linéaire par rapport à la taille du produit Cartésien. En d'autres termes, éviter la copie du tuple à chaque itération peut être significatif dans certaines situations.

cette version ne supporte pas d'itérateurs ou de gammes, mais c'est une implémentation directe simple qui utilise l'opérateur de multiplication pour représenter le produit cartésien, et un lambda pour effectuer l'action.

l'interface est conçue avec la fonctionnalité particulière dont j'avais besoin. J'avais besoin de la flexibilité nécessaire pour choisir les vecteurs sur lesquels appliquer le produit cartésien d'une manière qui n'obscurcit pas le code.

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

la mise en œuvre utilise recursion vers le haut de la structure de classe pour mettre en œuvre les boucles embarquées pour chaque vecteur. L'algorithme fonctionne directement sur les vecteurs d'entrée, ne nécessitant pas de grands tableaux temporaires. Il est facile de comprendre et de contester.

l'utilisation de std::fonction p_Action au lieu de void p_Action(long p_Depth, T *p_ParamList) pour le paramètre lambda me permettrait de capturer des variables locales, si je le voulais. Dans l'appel ci-dessus, Non.

mais vous le saviez, n'est-ce pas? "function" est une classe de template qui prend le paramètre type d'une fonction et la rend callable.

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