Wählen Sie Mengen von Zahlen {1,2,3} aus einer Reihe von Mengen {{..}, {..}, {..}} so dass alle Elemente eindeutig sind

Question

Ich bin an einem effizienten Algorithmus interessiert Führen Sie die folgende Aufgabe aus:

• Ich habe eine Reihe von Sets, die jeweils aus drei Nummern bestehen.
• Innerhalb einer solchen Teilmenge sind die Nummern eindeutig.
• Sie können jedoch mehrmals in anderen Teilmengen auftreten.
• Das Ziel ist, z.B. 3 Teilmengen, so dass die Elemente nur einmal vorkommen.

Zum Beispiel: {{1,2,3}, {3,4,5}, {6,7,8}, {5,7,9}}

• die zweite Teilmenge hat 3 gemeinsam mit der ersten Teilmenge.
• Die vierte Teilmenge hat ein Element mit der zweiten und dritten Teilmenge gemeinsam.
• Wenn jetzt eine Anzahl von Teilmengen ausgewählt wird, kann das nicht sein. Jedes Element kann nur einmal vorkommen.

Ich implementierte etwas, das den Job erledigt, aber ich denke, dass kann effizienter durchgeführt werden. Wie? vielleicht gibt es sogar einen Konstant-Zeit-Algorithmus mit map s oder so?

• Ich benutzte einen list den Satz für die Implementierung, weil ich gepflückt entfernen oder ausgeschlossen Subsets (schnell entfernen).
• Subsets werden unter Verwendung von vector s implementiert.
• Um bereits gewählte Nummern zu verfolgen, verwende ich eine set.

Watch it here.

#include <iostream> 
#include <vector> 
#include <list> 
#include <set> 
#include <iterator> 
#include <algorithm> 
#include <random> 

using namespace std; 

random_device rd; 
mt19937 rng(rd()); 

// pickes a random entry from a vector and returns an iterator to that element. 
list<vector<int>>::iterator randomEntry(list< vector<int> >& v) 
{ 
    uniform_int_distribution<int> dis(0, v.size()-1); // guaranteed unbiased 
    auto it{ begin(v) }; 
    advance(it, dis(rng)); 
    return it; 
} 

int main() 
{ 
    // a collection of possible sets 
    list< vector<int> > collection; 
    collection.emplace_back(vector<int>{51,9,22}); 
    collection.emplace_back(vector<int>{11,5,74}); 
    collection.emplace_back(vector<int>{61,9,35}); // 2nd element in common with 1st entry 
    collection.emplace_back(vector<int>{19,54,66}); 
    collection.emplace_back(vector<int>{53,86,35}); // 3rd element in common with 3rd entry 
    collection.emplace_back(vector<int>{11,3,55}); // 1st element in common with 2nd entry 

    // pick three -independent- sets form the collection 
    vector< vector<int> > picked; 
    set<int> elements; 

    while(picked.size()<3) 
    { 
    auto entry{ randomEntry(collection) }; // iterator to a randomly choosen entry 

    bool unused{ true }; 
    for(const auto i : *entry) 
    { 
     if(elements.find(i) != cend(elements)) // if it already exists in elements, its already used. 
     unused= false; 
    } 
    if(unused) 
     picked.emplace_back(*entry); 
    collection.erase(entry); // in any chase, remove == don't pick it again. 
    } 

    // all the elements printed should only appear once. 
    for(const auto& i : collection) 
    { 
    for(const auto j : i) 
     cout<<j<<" "; 
    cout<<endl; 
    } 

    return 0; 
} 

Answer 1

Erstellen einer Karte (hash in C++)

Iterieren über die Sätze.

Für jeden Satz prüfen, ob eine der Zahlen in der Karte ist. Wenn nicht, fügen Sie die Zahlen der Karte hinzu und fügen Sie diesen Satz zu den eindeutigen Sätzen hinzu, wenn es in der Karte ist, fahren Sie mit dem nächsten Satz fort.

Answer 2

Ich habe eine Reihe von Sets, die jeweils aus drei Nummern bestehen.

... Das Ziel ist, z.B. 3 Teilmengen, so dass die Elemente nur einmal vorkommen.

... aber ich denke, dass kann effizienter durchgeführt werden. Wie?

Da Ihr Ziel ist es, eine beliebige Anzahl p disjunkter Teilmengen (mit 3 als Beispiel) zu holen, dann ist dies genau das Set Packing problem, die eine der Karp's 21 NP-complete problems ist.

In der Frage erwähnen Sie, dass jeder Satz 3 Elemente hat (diesmal nicht als Beispiel). Leider ist diese Version immer noch NPC. Glücklicherweise bedeutet dies jedoch, dass there is an approximation algorithm with with a factor of ~50%.

Es ist daher äußerst unwahrscheinlich, dass Sie einen polynomiellen Algorithmus finden, der dies für einen allgemeinen p löst. Wenn ich auf deinen Code schaue, bin ich mir sicher, dass er korrekt ist. Es ist ein (zufälliger) Greedy-Algorithmus, und es scheint möglich, Szenarien (Eingaben + Zufallsauswahl) zu konstruieren, bei denen pessimistisch behauptet wird, dass es keine Lösung gibt.