在许多向量的组合上实现迭代器 [英] Implementing an iterator over combinations of many vectors

问题描述

我正在研究一个问题，需要迭代一次采取一个 K 元素的所有元素组合。例如，对于 K = 2 向量 v1 = [0 1] 和 v2 = [ 3 4] ，我会迭代（0,3），（0,4），（1,3），（1,4）。

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).

由于 K 是在运行时确定的，所以我不能使用显式for循环。我目前的方法是基于这个解决方案，它实现了一个里程表，为每个向量增加一个索引。

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

输出：

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 ]

然而，这有点凌乱，需要大量的样板代码，为了清楚起见，我宁愿转移到其他地方。理想情况下，我希望有一个自定义迭代器类，比如说 my_combination_iterator ，这样可以让我做得更干净，例如：

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

到目前为止，我已经看过 Boost iterator_facade 。但我的情况似乎比教程中的情况更复杂，因为我需要一个迭代器而不是 Value 的向量，而不是单个值类型来定义所需的运算符自定义迭代器。
如何实现这样的迭代器？

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?

推荐答案

为什么要使用自定义迭代器？
我们可以实现一个非常简单的类来迭代所有组合：

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

现场演示

更新：
如果您仍想使用迭代器，我建议迭代组合。可以将 Combinator 中的所有组合放入容器中，然后使用容器自己的迭代器。在我看来，这是一个更清洁的解决方案。唯一的缺点是显式存储所有组合所需的额外内存。

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.

这篇关于在许多向量的组合上实现迭代器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！