Sammlung von maximal disjunkten Mengen

Question

Bei einer Sammlung von 3 Zahlen finden Sie die maximalen disjunkten Mengen. Zum Beispiel sei C = {(3,4,5), (4,5,6), (1,2,3), (6,9,10), (7,8,9)}. Diese Eingabe sollte 3 zurückgeben, da die maximalen disjunkten Mengen {(1,2,3), (4,5,6), (7,8,9)} sind. Wie kann ich ein Programm schreiben, das die Sammlung der maximalen disjunkten Sätze ausgibt?

Ich habe über den Start durch Auswahl aller 5 Sätze gedacht. Schauen Sie sich dann die einzelnen Sets an und schauen Sie, ob das Entfernen dieses Elements den Rest der Sets beeinflusst. Wenn wir (3,4,5) wegnehmen, wird es uns erlauben, (4,5,6) und (1,2,3) zu behalten. Daher ist sein Nettogewinn +1. Wir sollten es aus unserer endgültigen Liste entfernen. Wenn wir dann (4,5,6) wegnehmen, können wir es behalten (6,9,10). Der Nettonutzen ist 0, also entferne es nicht. Entfernen (1,2,3) wird nichts bewirken. Entferne es nicht. Das Entfernen (6, 9, 10) erlaubt es uns, (7, 8, 9) zu behalten. Ich bin mir nicht sicher, ob das irgendeinen Sinn ergibt, aber lass mich wissen, was du denkst!

Answer 1

Wenn die drei Zahlen immer aufeinanderfolgend sind, dann hat dies eine einfache dynamische Programmierlösung (berechnen Sie die maximalen Mengen, die mit den Zahlen 1..i unter Verwendung einer rekursiven Formel gesetzt werden können).

Wenn diese Einschränkung jedoch nicht immer zutrifft, ist dieses Problem NP schwer. Es ist NP schwer ist, weil es verwendet werden könnte, um die NP-vollständige 3-dimensional matching problem zu lösen.

Nehmen wir zum Beispiel an, wir sind Elemente in X, Y, Z zusammenpassen. Wir können Sets für jede erlaubte Übereinstimmung mit den Zahlen 1 .. | X | in der ersten Position, | X | +1 .. | X | + | Y | in der zweiten Position und | X | + | Y | .. | X | + | Y | + | Z | in der dritten Position. Sobald wir diese Mengen konstruiert haben, können wir das 3-dimensionale Anpassungsproblem lösen, indem wir einen Algorithmus verwenden, um dieses Problem zu lösen.

Answer 2

Greedy wird tun. Beachten Sie, dass die Drillinge sind tatsächlich Intervalle, die Mitte Anzahl keine Rolle spielt, nur der Start/Ende diejenigen tun (dh in [start, whatever, end] ignorieren whatever

The O(N log(N)) greedy solution

1. sortieren die Intervalle eine Beziehung Reihenfolge verwendet, die:

   • Orten diejenigen mit höheren Enden gegen das Ende (das heißt „[start _i, end _i] < [start _j, end _j] "iff " _i < Ende _j Ende"
   • mit gleichen Enden, die längeren höher sind (das heißt" [start _i, end] < [Start _j]“iff "

2. nehmen einen Stapel _j < Start _i") beginnen und schieben das letzte Segment in

3. scannen, um die Intervalle sortiert nach unten (der Index k Strom)

   • Wenn die " k start" ist höher als " _{starten Stapel-top}" (d.h.das Curr-Intervall lässt mehr Platz davor frei, knallt den oberen Teil des Stapels und drückt den aktuellen.
   • Wenn "start _Stack-top"> " _k Ende" - die aktuellen nicht mit Stapelkopf überlappt - einfach das aktuelle Intervall in dem Stapel drücken (ein Teil der Lösung ist).
   • sonst das aktuelle Intervall ignorieren (überlappt mit der besten Lösung, die wir bisher haben, gierig zu sein wir es nicht verlieren wollen)

Am Ende werden Sie die maximale Anzahl haben der nicht überlappenden Segmente in den Stapel, mit dem ganz links oben - das ist eine Raumkomplexität von O (N).
Wenn Sie sie nur zählen müssen, beachten Sie, dass nur der oberste Stapel im Vergleich beteiligt ist. Sie müssen sich also nur den oberen Teil des Stapels merken (jedes Mal, wenn Sie den oberen Stapel platzieren würden) mit der aktuellen und lassen Sie die count unverändert, jedes Mal, wenn Sie nur drücken, ersetzen Sie die "Top-of-Stack" und erhöhen Sie die Anzahl. Die Raumkomplexität zum Zählen ist also nur O (1).

---

Ihr Beispiel:

1. nach dem Sortierschritt, Sie haben Ihre Intervalle als {(1,2,3), (3,4,5), (4,5,6), (7,8,9), (6,9,10)}

2. Anfang des Stapels (6,9,10) - Zählung 1. Alle folgenden Schritte sind das Abrollen des Zyklus.

3. nehmen (7,8,9) - mehr konservativen Start, Vertreibung Top of Stack (aus mit dem alten) Push die aktuelle (in mit dem neuen) - Spitze des Stapels (7,8,9), zählen = 1.

4. (4,5,6) - endet früher als der Anfang des Stapels beginnt, sammeln Sie es - oben auf dem Stapel (4,5,6), zählen = 2;

5. (3,4,5) - kleinerer Start, überlappt aber mit der Spitze des Stapels. Sei gierig - ignoriere/verwerfe. Oberseite des Stapels (4,5,6), Zählung = 2;

6. (1,2,3) - endet früher als der Anfang des Stapels beginnt, sammeln Sie es - oben auf dem Stapel (1,2,3), zählen = 3;

Ende des Abwärtszyklus, wobei der Stapel von oben nach unten angezeigt: {(1,2,3}, (4,5,6), (7,8,9)} mit einer Zählung von 3.

---

C++ ( nicht getestet)

struct interval { int s; int e; } 

struct comparator { 
    bool operator(const interval& i1, const interval& i2) const { 
    int i=i1.e-i2.e; // higher ends placed last 
    if(0==i) { // higher length/lower starts will be higher 
     i=i2.s-i1.s; 
    } 
    return i<0; 
    } 
} 

int count_intervals(std::vector<interval>& sets) { 
    if(sets.empty()) return 0; 

    comparator comp; 
    std::sort(sets.begin(), sets.end(), comp); 

    /* if you need the solution as well, use a stack */ 
    // std::stack<std::vector> solution; 
    interval& stack_top=sets[sets.size()-1]; // solution.push(stack_top); 
    int count=1; // we have at least one in the stack 
    for(int i=sets.size()-2; i>=0; i--) { 
    interval& curr=sets[i]; 
    if(curr.s > stack_top) { // a better one, lets more room in front 
     stack_top=curr; // solution.pop(); solution.push(curr); 
    } 
    else if(curr.e < stack_top.s) { 
     stack_top=curr; // solution.push(curr); 
     count++; 
    } 
    } 
    // if you need the solution, arrange the params of the function to return it 
    return count; 
}