Wie bekomme ich 3 einzigartige Gegenstände aus 3 überlappenden Listen?

Question

Dies unterscheidet sich von der Suche nach eindeutigen oder eindeutigen Elementen auf jeder Liste.

Ich habe 3 Listen von Referenzobjekten, und jede Liste kann die gleichen Elemente enthalten (aber kann jedes Element nur einmal enthalten). Ich möchte eine Ja/Nein-Antwort auf die folgende Frage: Nimmt man in jeder Liste ein Element an, gibt es eine Möglichkeit, keine Duplikate zu haben?

Zum Beispiel:

Gesamtübersicht: Apfel, Birne, Banane

Liste 1: Apfel, Birne

Liste 2: Banane

Liste 3: Banane, Apfel

Resultat: WAHR (kann einen Gegenstand von jeder Liste wählen und hat 3 einzigartige Gegenstände)

Gesamtübersicht: Apfel, Birne, Banane

Liste 1: Apfel, Birne

Liste 2: Apfel, Birne

Liste 3: Apfel, Birne

Ergebnis: FALSCH (nicht wählen können ein Einzelteil von jeder Liste und haben 3 einzigartige Einzelteile)

Es ist für ein Spiel, also brauche ich es, um leistungsfähig zu sein! Danke im Voraus.

Answer 1

Dies ist NP-Hard Problem Constraint satisfaction problemsee here. Mit anderen Worten: Sie haben Gruppe {a, b, c, d} und Sie wollen (a or b) and (b or c) and...

Aber finden, wenn Sie alle möglichen Optionen voraus wissen, können Sie eine Liste \ Wörterbuch der Werte (gehasht Werte schaffen für kleinere Listen) und überprüfen Sie die Liste in Runtime.

Wenn nicht, können Sie einen der CSP-Lösungsalgorithmen verwenden.

Answer 2

Lassen Sie uns sagt, dass Sie die Liste haben α, β und ɣ.

Lassen ABC = α ∩ β ∩ ɣ
Lassen AB = α ∩ β \ ABC
Lassen AC = α ∩ ɣ \ ABC
Lassen BC = β ∩ ɣ \ ABC
Lassen A = α \ (β ∪ ɣ)
Lassen B = β \ (α ∪ ɣ)
Lassen C = ɣ \ (α ∪ β)

Let | X | sei die Kardinalität von Menge X.

return true, wenn und nur wenn |A| + |B| + |C| + |AB| + |AC| + |BC| + |ABC| >= 3

Beispielimplementierung:

void Main() 
{ 
    var alpha = new List<string> { "apple", "pear", }; 
    var beta = new List<string> { "banana", }; 
    var gamma = new List<string> { "banana", "apple", }; 

    Console.WriteLine(Compute(alpha, beta, gamma)); 
    Console.WriteLine(ComputeWithSets(alpha, beta, gamma)); 

    alpha = new List<string> { "apple", "pear", }; 
    beta = new List<string> { "apple", "pear", }; 
    gamma = new List<string> { "apple", "pear", }; 

    Console.WriteLine(Compute(alpha, beta, gamma)); 
    Console.WriteLine(ComputeWithSets(alpha, beta, gamma)); 

    alpha = new List<string> { "apple", "pear", "banana", }; 
    beta = new List<string> { "apple", "pear", "banana", }; 
    gamma = new List<string> { "apple", "pear", "banana", }; 

    Console.WriteLine(Compute(alpha, beta, gamma)); 
    Console.WriteLine(ComputeWithSets(alpha, beta, gamma)); 
} 

bool Compute(List<string> alpha, List<string> beta, List<string> gamma) 
{ 
    if (alpha.Count == 0) return false; 
    if (beta.Count == 0) return false; 
    if (gamma.Count == 0) return false; 

    foreach (var a in alpha) 
     foreach (var b in beta) 
      if (a != b) 
       foreach (var c in gamma) 
        if (c != a && c != b) 
        { 
         Console.Write(string.Format("{0},{1},{2} =>", a, b, c)); 
         return true;  
        } 
    return false; 
} 

bool ComputeWithSets(List<string> alpha, List<string> beta, List<string> gamma) 
{ 
    var abc = alpha.Intersect(beta.Intersect(gamma)); 
    var abcCardinality = abc.Count(); 

    var count = abcCardinality; 
    if (count >= 3) return true; 

    var ab = alpha.Intersect(beta).Except(abc); 
    count += ab.Count(); 
    if (count >= 3) return true; 

    var bc = beta.Intersect(gamma).Except(abc); 
    count += bc.Count(); 
    if (count >= 3) return true; 

    var ac = alpha.Intersect(gamma).Except(abc); 
    count += ac.Count(); 
    if (count >= 3) return true; 

    var a = alpha.Except(ab).Except(ac).Except(abc); 
    count += a.Count(); 
    if (count >= 3) return true; 

    var b = beta.Except(ab).Except(bc).Except(abc); 
    count += b.Count(); 
    if (count >= 3) return true; 

    var c = gamma.Except(ac).Except(bc).Except(abc); 
    count += c.Count(); 
    if (count >= 3) return true; 

    return false; 
} 

Answer 3

Ich denke, man könnte es tun, wie folgt:

Sie nehmen das erste Element in Ihrer gesamten Liste und dann prüfen, Jede Ihrer 3 "Ziel" -Listen, um zu sehen, wo sie auftritt. Speichern Sie diese Prüfergebnisse in einem 3-Elemente-Array (1 Element für jede Ihrer Ziellisten) - sagen Sie 0 für tritt nicht auf und 1 für tritt auf. Dann tun Sie dies wieder für den 2. Punkt in Ihrer Gesamtliste und so weiter. Sie erhalten also eine "Checkliste" mit 3 Elementarrays (die Listenlänge entspricht der Anzahl der Elemente auf Ihrem gesamten Array. ) Dann summieren Sie das erste Element jedes Arrays in Ihrer Checkliste, das zweite . Element und das dritte Element Solange die jede Summe größer als 0 Ihr Test ist passiert

zB für Ihr erstes Beispiel Gesamtübersicht:. Apfel, Birne, Banane

Check results: 
Item 1 (apple) : 1 0 1 (apple occurs in list 1 and 3) 
Item 2 (pear) : 1 0 0 
Item 3 (banana) : 0 1 1 
Total    2 1 2 (result is a pass) 

Ihr zweites Beispiel wird fehlschlagen weil Sie zwei Checkarrays von 1 1 0 haben und wenn Sie das dritte Element von jedem dieser Arrays addieren, erhalten Sie 0.

Ich denke, das kann leicht auf so viele Ziellisten erweitert werden, wie Sie wollen - wenn Sie n Listen haben, werden Ihre Check-Arrays jeweils n Elemente enthalten.