C ++如何以特定模式遍历向量的不同集合元素

Question

我有一个包含整数的集合向量，如下所示：

std::vector<std::set<int> > vec = {{2,4},{1,3,8},{7,5}};

上述集合向量的示意图

| 2 | 4 |       
| 1 | 3 | 8 |
| 7 | 5 |

我需要遍历向量的每个集合元素，使得向量行中的每个集合元素访问下一行中的每个集合元素，依此类推。

例如，vector第一行集合的第一个元素（即2）将访问第二行的第一个元素（即1），然后访问第三行的第一个元素（即7）。同样，这些遍历将按如下顺序排列：

First vector row and first set element -> Second vector row and first set element -> Third vector row and first set element
First vector row and first set element -> Second vector row and first set element -> Third vector row and second set element
First vector row and first set element -> Second vector row and second set element -> Third vector row and first set element
First vector row and first set element -> Second vector row and second set element -> Third vector row and second set element 
First vector row and first set element -> Second vector row and third set element -> Third vector row and first set element
First vector row and first set element -> Second vector row and third set element -> Third vector row and second set element

First vector row and second set element -> Second vector row and first set element -> Third vector row and first set element
First vector row and second set element -> Second vector row and first set element -> Third vector row and second set element
First vector row and second set element -> Second vector row and second set element -> Third vector row and first set element
First vector row and second set element -> Second vector row and second set element -> Third vector row and second set element 
First vector row and second set element -> Second vector row and third set element -> Third vector row and first set element
First vector row and second set element -> Second vector row and third set element -> Third vector row and second set element

结果向量应该是一个列表向量，其每个元素如下：

std::vector<std::list<int> > list = {{2,1,7},{2,1,5},{2,3,7},{2,3,5},{2,8,7},{2,8,5},{4,1,7},{4,1,5},{4,3,7},{4,3,5},{4,8,7},{4,8,5}};

列表的合成向量示意图

| 2 | 1 | 7 |
| 2 | 1 | 5 | 
| 2 | 3 | 7 |
| 2 | 3 | 5 |
| 2 | 8 | 7 |
| 2 | 8 | 5 |
| 4 | 1 | 7 |
| 4 | 1 | 5 | 
| 4 | 3 | 7 |
| 4 | 3 | 5 |
| 4 | 8 | 7 |
| 4 | 8 | 5 |

在 C++ 中实现此目的的最有效方法是什么？

Answer 1

让我们将其分解为几个步骤：

// Add the int to a copy of the list
std::list<int> append_copy(std::list<int> l, int i)
{
    l.push_back(i);
    return l;
}

// append_copy the list for each element in the set
template<typename OutputIterator>
OutputIterator cross_append(const std::set<int>& s, const std::list<int>& l, OutputIterator d_first)
{
    return std::transform(s.begin(), s.end(), d_first, [&](int i){ return append_copy(l, i); });
}

std::vector<std::list<int> > cross_apply(const std::vector<std::set<int> > & vec)
{
    // start with a single empty list
    std::vector<std::list<int> > result{ {} };

    // loop over the input to get the sets
    for (auto& s : vec)
    {
        std::vector<std::list<int> > inner;
        auto it = std::back_inserter(inner);

        // loop over the last run's intermediate, duplicating it
        for (auto& l : result)
        {
             it = cross_append(s, l, it);
        }
        result = inner;
    }
    return result;
}

See it live

Answer 2

标准库中没有现成的解决方案来枚举来自多个集合 AFAIK 的元素组合。

下面是 next_combination 函数的实现，其工作方式与 std::next_permutation 类似。

// advance to next combination, return false if already last combination
template <typename SetOfSetsIter, typename CombinationIter>
bool next_combination(
    CombinationIter combFirst, SetOfSetsIter dataFirst, SetOfSetsIter dataLast)
{
    for(; dataFirst != dataLast; ++dataFirst, ++combFirst)
    {
        if(++(*combFirst) != dataFirst->end())
            return true;
        *combFirst = dataFirst->begin();
    }
    return false;
}

// make combination from first elements of set's sets as a vector
template <typename SetOfSetsIter>
std::vector<typename std::iterator_traits<SetOfSetsIter>::value_type::const_iterator>
first_combination(SetOfSetsIter dataFirst, SetOfSetsIter dataLast)
{
    std::vector<typename std::iterator_traits<SetOfSetsIter>::value_type::const_iterator>
        combination;
    for(; dataFirst != dataLast; ++dataFirst)
        combination.push_back(dataFirst->cbegin());
    return combination;
}

用法：

typedef std::vector<int> Set;
typedef std::vector<Set> SetOfSets;
const SetOfSets data = {{2, 4}, {1, 3, 8}, {7, 5}};
std::vector<Set::const_iterator> comb = first_combination(data.cbegin(), data.cend());
std::cout << "First to last:" << std::endl;
do
{
    for(const auto& it : comb)
        std::cout << *it << " ";
    std::cout << std::endl;
} while(next_combination(comb.begin(), data.cbegin(), data.cend()));
comb = first_combination(data.cbegin(), data.cend());

std::cout << "\nLast to first:" << std::endl;
do
{
    for(const auto& it : comb)
        std::cout << *it << " ";
    std::cout << std::endl;
} while(next_combination(comb.rbegin(), data.crbegin(), data.crend()));

Live Demo

C ++如何以特定模式遍历向量的不同集合元素

C++ How to traverse through different set elements of a vector in specific pattern

c++

algorithm

traversal