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

Question

I have a vector of sets which contain integers as given below:

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

Diagram illustration of the above vector of set

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

I need to traverse through each set elements of vector such that each set element in vector row visits every set element in the next row and so on.

For example, the first element of the set in first row of vector (i.e 2) will visit the first element of second row (i.e 1) and then visit the first element of third row (i.e 7). Similarly, these traversals will be in the order as below:

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

The resultant vector should be a vector of list with each of its elements as below:

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

Diagram illustration of the resultant vector of 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 |

What would be the most efficient way to achieve this in C++?

Please describe the desired pattern, don't make us guess it from a sample. Also, in your samples, are individual sets rows or columns? Is it [{2,1,7}, {4,3,5} {8}]? Or some other combination? — , May 24 '18 at 12:49
AFAIK there's no ready solution for calculating combinations in standard library (which is bad, since this question pops up quite often on SO). One could adapt [this](https://stackoverflow.com/a/46569927/1597714) approach to work with desired container types, or make it generic based on iterators. — AMA, May 24 '18 at 13:03
Thanks for all your effort guys, I have edited my description to make it easier to understand. — Satish Jaiswal, May 24 '18 at 13:47
Is it meant to be the case that `7` precedes `5` for the final digit in the output? — Caleth, May 24 '18 at 13:57
@Caleth Not necessary, your solution gives the desired output. Can you also please share some light on its time complexity? — Satish Jaiswal, May 24 '18 at 14:14
let `N` be the length of vec, and `S` be the product of it's element's `size`s, it will be `O(N*N*S)` I don't think you can do better — Caleth, May 24 '18 at 14:21
[This answer](https://stackoverflow.com/a/1703575/5376789) is a nice solution. — xskxzr, May 24 '18 at 15:22
@xskxzr The solution (especially recursive one) is nice indeed, very helpful. Thanks! — Satish Jaiswal, Jun 03 '18 at 15:11

Caleth · Accepted Answer · 2018-05-24T14:00:19.537

Let's break down this into a couple of steps:

// 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

Thanks @Caleth, much appreciated! – Satish Jaiswal May 24 '18 at 15:00 — Satish Jaiswal, May 24 '18 at 15:00

AMA · Answer 2 · 2018-05-27T07:53:56.653

There's no ready solution in standard library for enumerating combinations of elements from several sets AFAIK.

Here's the implementation of next_combination function that works similarly to 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;
}

Usage:

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

This looks to use Java style iteration rather than C++ style iteration — Caleth, May 24 '18 at 14:22
@Caleth do you mean that MultiSetCombinator could be a proper custom iterator? If yes, I don't have experience with writing custom iterators in C++. But it would be great to see how it could be done in this case. — AMA, May 24 '18 at 14:26
You move the incrementy part of `next` to `operator++`, and the booly part to `operator==`, and provide a default constructor for the end of the range, and then add a bunch of typedefs such that `std::iterator_traits` gets a proper instantiation — Caleth, May 24 '18 at 14:31
@Caleth after giving it more thought, I updated the answer to follow an `std::next_permutation`-like approach (which is more fitting IMO) — AMA, May 25 '18 at 11:04

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

2 Answers2