0

ハイパーエッジの 2 次元ベクトルと隣接リストがあります。ベクトルの和集合を見つけなければなりませんがhyperEdges[i].size()、たった 2 つのベクトルの和集合しか見つけることができません。これを行うには、以下のコードにどのような改善を加えることができますか? 共用体を新しく宣言された 2-D ベクトルに格納したいconnectedEdges 

void find_union()
{
    connectedEdges.resize(nEdges+1);
    for(int i = 1; i <= nEdges; i++)
    {
        vector<int>::iterator it;
        connectedEdges[i].resize(nEdges+1);

        for(int j = 1; j < hyperEdges[i].size()-1; j++)
        {
            int p = hyperEdges[i][j-1];
            int q= hyperEdges[i][j];
            it = set_union(adjL[p].begin(), adjL[p].end(),adjL[q].begin(),adjL[q].end(), connectedEdges[i].begin());
        connectedEdges[i].resize(it-connectedEdges[i].begin());
        }
    }    
}

例 ： {1,2,4,6,8}

{1,2,3,5,6}

{1,4,7,13,15}

これらの 3 つのセットの和集合{1,2,3,4,5,6,7,8,13,15} は{1,2,3,4,5,6,8}

4

3 に答える 3

1

anxieuxが示唆するように、それらをに移動してset元に戻すことができます。または、それらすべてを直接手動で繰り返すこともできます。

#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>

std::vector<int> find_union(const std::vector<std::vector<int>>& vecs)
{
    using iter = std::vector<int>::const_iterator;
    using pr = std::pair<iter, iter>;

    // construct pairs of iterators into each vector
    // we will iterate over all of these simultaneously
    std::vector<pr> iter_pairs;
    std::vector<int> results;

    iter_pairs.reserve(vecs.size());
    for (auto& v : vecs) {
        iter_pairs.emplace_back(v.begin(), v.end());
    }   

    while (!iter_pairs.empty()) {
        // pick the next smallest element
        int m = *std::min_element(iter_pairs.begin(), iter_pairs.end(), [](const pr& a, const pr& b){ 
                    return *a.first < *b.first;
                })->first;

        // add it to our results
        results.push_back(m);

        // any vector that contained this element should be advanced
        // if we're done with that vector, remove it
        iter_pairs.erase(
            std::remove_if(iter_pairs.begin(), iter_pairs.end(), [=](pr& p){ 
                if (*p.first == m) {
                    ++p.first;
                    return p.first == p.second;
                }   
                return false;
            }), 
            iter_pairs.end()
            );  
    }   

    return results;
}

int main() {
    for (int i : find_union({{1,2,3}, {1,2,4}, {3,5,42}})) {
        std::cout << i << ' '; // prints 1 2 3 4 5 42
    }   
    std::cout << std::endl;
}
于 2015-04-30T13:25:22.857 に答える