C ++ Как пройти через различные элементы набора вектора в определенном образце - PullRequest
Новая
       5

C ++ Как пройти через различные элементы набора вектора в определенном образце

0 голосов
/ 24 мая 2018

У меня есть вектор наборов, которые содержат целые числа, как указано ниже: 

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

Диаграмма иллюстрации вышеуказанного вектора набора 

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

Мне нужно пройти через элементы каждого наборавектора так, что каждый элемент набора в строке вектора посещает каждый элемент набора в следующей строке и так далее.

Например, первый элемент набора в первой строке вектора (т. Е. 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 ++?

Ответы [ 2 ]

0 голосов
/ 24 мая 2018

В стандартной библиотеке нет готового решения для перечисления комбинаций элементов из нескольких наборов 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;
}
* 1007.* Использование: 
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()));

Демонстрация в реальном времени

0 голосов
/ 24 мая 2018

Давайте разберем это на пару шагов: 

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

Посмотрим вживую

...