Implementing an iterator over combinations of many vectors

Question

I am working on a problem that requires iterating over all combinations of elements of K vectors taken one at a time. So for example for K=2 vectors v1 = [0 1] and v2 = [3 4], I would iterate over (0,3), (0,4), (1,3), (1,4).

Since K is determined at run-time, I cannot use explicit for loops. My current approach is based on this solution that implements an "odometer" incrementing an index for each vector.

#include <vector> #include <iostream> int main(int argc, char * argv[]) { std::vector<int> v1( {1, 2, 3} ); std::vector<int> v2( {-2, 5} ); std::vector<int> v3( {0, 1, 2} ); std::vector<std::vector<int> > vv( {v1, v2 ,v3} ); // Iterate combinations of elems in v1, v2, v3, one at a time std::vector<std::vector<int>::iterator> vit; for (auto& v : vv) vit.push_back(v.begin()); int K = vv.size(); while (vit[0] != vv[0].end()) { std::cout << "Processing combination: ["; for (auto& i : vit) std::cout << *i << " "; std::cout << "]\n"; // increment "odometer" by 1 ++vit[K-1]; for (int i = K-1; (i > 0) && (vit[i] == vv[i].end()); --i) { vit[i] = vv[i].begin(); ++vit[i-1]; } } return 0; }

Output:

Processing combination: [1 -2 0 ] Processing combination: [1 -2 1 ] Processing combination: [1 -2 2 ] Processing combination: [1 5 0 ] Processing combination: [1 5 1 ] Processing combination: [1 5 2 ] Processing combination: [2 -2 0 ] Processing combination: [2 -2 1 ] Processing combination: [2 -2 2 ] Processing combination: [2 5 0 ] Processing combination: [2 5 1 ] Processing combination: [2 5 2 ] Processing combination: [3 -2 0 ] Processing combination: [3 -2 1 ] Processing combination: [3 -2 2 ] Processing combination: [3 5 0 ] Processing combination: [3 5 1 ] Processing combination: [3 5 2 ]

However, this is somewhat messy and requires a lot of boilerplate code that I'd rather move elsewhere for clarity. Ideally I would like to have a custom iterator class, say my_combination_iterator, that would allow me to do things much cleaner, e.g.:

for (my_combination_iterator it = vv.begin(); it != vv.end(); ++it) // process combination

So far, I have looked at Boost iterator_facade. But my case seems more complicated than the one in the tutorial since I would need an iterator over a vector of Values as opposed to a single value type to define the required operators for the custom iterator. How could such an iterator be implemented?

I finally had some spare-time to try implementing a proper bi-directional combinations iterator. You can find it here. I did not use boost, so the code is more verbose than it could be. — AMA
– AMA, Commented Jun 4, 2018 at 10:08

AMA · Accepted Answer · 2017-10-05 10:01:09Z

Why would you like to use custom iterators? One could instead implement a very simple class that will iterate through all combinations:

class Combinator { public: Combinator(std::vector<std::vector<int> >& vectors) : m_vectors(vectors) { m_combination.reserve(m_vectors.size()); for(auto& v : m_vectors) m_combination.push_back(v.begin()); } bool next() { // iterate through vectors in reverse order for(long long i = m_vectors.size() - 1; i >= 0; --i) { std::vector<int>& v = m_vectors[i]; std::vector<int>::iterator& it = m_combination[i]; if(++it != v.end()) return true; it = v.begin(); } return false; } std::vector<std::vector<int>::iterator> combination() const { return m_combination; } private: std::vector<std::vector<int> >& m_vectors; // reference to data std::vector<std::vector<int>::iterator> m_combination; };

Live Demo

UPDATE: If you would still like to use iterators, I suggest iterating over combinations. One can put all the combinations from Combinator into a container and then work with container's own iterators. In my opinion it's a cleaner solution. The only drawback is the extra-memory needed to store all combinations explicitly.

This is practically an iterator. Add the missing operators, add a default constructor, inherit from std::iterator and you're there.
This is a reasonable suggestion. I am interested in using a custom iterator as it would allow to directly apply STL algorithms that work on iterator ranges. I think it would also be still clearer in signaling the intent of how to use the code.
@mikkola you can put all the combinations from Combinator into a container and then work with container's iterators. IMO it's a cleaner solution. The only drawback is the memory overhead needed to store all combinations explicitly.
@AMA in the end I went with a slight variation of this, so I'm accepting this as an answer. Thanks for your time!

Collectives™ on Stack Overflow

Implementing an iterator over combinations of many vectors

1 Answer 1

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Linked

Related