Schnittmenge mit mehreren Mengen



  • Hallo,

    ich habe eine beliebige Zahl an Zahlenmengen, die immer zusammenhängend sind. Soll heißen sie fangen zu Beispiel bei 2 an und hören bei 10 auf (gibt es ein besseres Wort dafür?).
    Von diesen Mengen ist eine die Referenzmenge, deren Überlappung mit einer beliebigen Anzahl andere Mengen berechnet werden soll. Ich finde es in Worten schwer zu beschreiben von daher hier mal eine grafische Veranschaulichung:

    ---------------------------------------           Referenz
         ------------------                                             Set 1
                                  ----------------                      Set 2
                         -------------                                  Set 3
                                                          ---------     Set 4
    _______________________________________________________________________________
                      ----------------------------        ---           in %
    

    Die Überlappung mit einer Menge ist sehr einfach zu bestimmen, aber bei mehreren tue ich mir echt schwer, da diese auch überlappen können etc. Alle meine Lösungen sind extrem schwerfällig mit zig Fallunterscheidungen und funktionieren dadurch auch teilweise nicht richtig. Aber irgendwie stehe ich bei diesem Problem auf dem Schlauch eine schlanke, performante Lösung zu finden.
    Hat jemand vielleicht einen guten Lösungsansatz für dieses Problem?
    Vielen Dank schonmal!



  • Du suchst also Referenz(Set1Set2Set3Set4)\mathrm{Referenz} \cap (\mathrm{Set1} \cup \mathrm{Set2} \cup \mathrm{Set3} \cup \mathrm{Set4})?



  • Diese "Zahlenmengen, die immer zusammenhängend sind" nennt man "Intervalle".

    Sei RR das Referenzintervall und M\_1, \dots, M\_n die Testmengen, dann möchtest du, wenn ich dich richtig verstanden habe, berechnen:
    R(i=1nMi)R \cap \left(\bigcup\limits_{i=1}^n M_i\right)

    Du könntest zum Beispiel die zu vereinigenden Mengen sortieren nach ihrem Startwert. Dann vereinigst du eine Menge solange mit den nächstfolgenden, wie dadurch kein "Loch" entsteht. Dann berechnest du damit die Schnittmenge zur Referenz. Dann machst du mit der nächstfolgenden Testmenge weiter usw. usf.

    Gibt bestimmt auch noch andere Lösungen, das ist jetzt nur eine schnelle Lösungsidee.

    Was diese Aufgabe dann vielleicht noch etwas anspruchsvoller macht in der Implementierung: bedenke auch, dass es offene, halboffene und geschlossene Intervalle gibt.


  • Mod

    Simple Variante für halboffene Intervalle.

    #include <iostream>
    #include <iterator>
    #include <set>
    #include <type_traits>
    #include <utility>
    
    struct interval {
        // Invariant: lbound < rbound
        int lbound;
        int rbound;
    };
    bool operator<(const interval& lhs, const interval& rhs) {
        return lhs.rbound < rhs.lbound; // induces total ordering if intervals not connected
    }
    std::ostream& operator<<(std::ostream& s, const interval& i) {
        return s << '[' << i.lbound << ',' << i.rbound << ')';
    }
    
    void merge(std::set<interval>& s, interval i) {
        auto [first, last] = s.equal_range(i);
        if (first == last) {
            s.insert(last, i);
            return;
        }
        i.lbound = std::min(i.lbound, first->lbound);
        i.rbound = std::max(i.rbound, prev(last)->rbound);
        s.insert(s.erase(first, last), i);
    }
    
    template <typename Iter, std::enable_if_t<std::is_same_v<typename std::iterator_traits<Iter>::value_type, interval>, int> = 0>
    std::set<interval> merge(Iter first, Iter last) {
        std::set<interval> result;
        for (;first != last; ++first)
            merge(result, *first);
        return result;
    }
    
    std::set<interval> intersect(const std::set<interval>& s, interval i) {
        std::set<interval> result;
        auto [first, last] = s.equal_range(i);
        if (first == last)
            return result;
        auto lbound = std::max(i.lbound, first->lbound);
        auto rbound = std::min(i.rbound, first->rbound);
        if (lbound != rbound)
            result.insert({ lbound, rbound });
        if (++first == last--)
            return result;
        result.insert(first, last);
        lbound = last->lbound;
        rbound = std::min(i.rbound, last->rbound);
        if (lbound != rbound)
            result.insert(result.end(), { lbound, rbound });
        return result;
    }
    
    #include <vector>
    int main() {
        std::vector<interval> sets{ { 0, 30 }, { 40, 70 }, { 20, 60 }, { 80, 100 } };
        for (auto& x : sets)
            std::cout << x << ',';
        interval reference{ 10, 90 };
        std::cout << '\n' << reference << '\n';
        for (auto& x : intersect(merge(sets.begin(), sets.end()), reference))
            std::cout << x << ',';
        std::cout << '\n';
    }
    

Log in to reply