Überprüfen Sie, ob ein Array eine Teilmenge eines anderen Arrays ist

145

Haben Sie eine Idee, wie Sie überprüfen können, ob diese Liste eine Teilmenge einer anderen ist?

Insbesondere habe ich

List<double> t1 = new List<double> { 1, 3, 5 };
List<double> t2 = new List<double> { 1, 5 };

Wie kann mit LINQ überprüft werden, ob t2 eine Teilmenge von t1 ist?

Graviton
quelle
Wenn die Listen sortiert sind (wie in Ihrem Beispiel), sollte dies in O (n + m) möglich sein.
Colonel Panic

Antworten:

255
bool isSubset = !t2.Except(t1).Any();
Cameron MacFarland
quelle
1
Ich habe die Erweiterungsmethode geekswithblogs.net/mnf/archive/2011/05/13/… erstellt
Michael Freidgeim
@Bul Ikana Die Arbeit mit diesem Code ist einfach. Die Erweiterungsmethode ruft intern Equals und GetHashCode der überschriebenen Objektklassenmethoden auf, wenn für den Job kein IEqualityComparer bereitgestellt wird.
Mrinal Kamboj
2
Wenn die Listen die Länge n und m haben, wie hoch ist die zeitliche Komplexität dieses Algorithmus?
Colonel Panic
2
Wäre schön, wenn dies auf eine Linq-Methode namens ContainsAll
Sebastian Patten
60

Verwenden Sie HashSet anstelle von List, wenn Sie mit Sets arbeiten. Dann können Sie einfach IsSubsetOf () verwenden

HashSet<double> t1 = new HashSet<double>{1,3,5};
HashSet<double> t2 = new HashSet<double>{1,5};

bool isSubset = t2.IsSubsetOf(t1);

Entschuldigung, dass LINQ nicht verwendet wird. :-(

Wenn Sie Listen verwenden müssen, funktioniert die Lösung von @ Jared mit der Einschränkung, dass Sie alle vorhandenen wiederholten Elemente entfernen müssen.

Tvanfosson
quelle
3
Genau. Wenn Sie eine Set-Operation wünschen, verwenden Sie die dafür vorgesehene Klasse. Camerons Lösung ist kreativ, aber nicht so klar / ausdrucksstark wie das HashSet.
technophile
2
Ähm, ich bin anderer Meinung, weil die Frage speziell "LINQ verwenden" lautet.
JaredPar
9
@ JarPar: Na und? Ist es nicht besser, jemandem den richtigen Weg zu zeigen, als den Weg, den er gehen möchte?
Jonathan Allen
Eine Liste behält ihre Reihenfolge bei, ein Satz jedoch nicht. Wenn die Reihenfolge wichtig ist, würde dies zu falschen Ergebnissen führen.
UuDdLrLrSs
11

Wenn Sie Unit-Tests durchführen , können Sie auch die CollectionAssert.IsSubsetOf- Methode verwenden:

CollectionAssert.IsSubsetOf(subset, superset);

Im obigen Fall würde dies bedeuten:

CollectionAssert.IsSubsetOf(t2, t1);
Géza
quelle
7

Dies ist eine wesentlich effizientere Lösung als die anderen hier veröffentlichten, insbesondere die Top-Lösung:

bool isSubset = t2.All(elem => t1.Contains(elem));

Wenn Sie in t2 ein einzelnes Element finden, das nicht in t1 enthalten ist, wissen Sie, dass t2 keine Teilmenge von t1 ist. Der Vorteil dieser Methode besteht darin, dass sie im Gegensatz zu den Lösungen mit .Except oder .Intersect direkt vor Ort durchgeführt wird, ohne zusätzlichen Speicherplatz zuzuweisen. Darüber hinaus kann diese Lösung unterbrochen werden, sobald ein einzelnes Element gefunden wird, das gegen die Teilmengenbedingung verstößt, während die anderen weiter suchen. Unten ist die optimale Langform der Lösung aufgeführt, die in meinen Tests nur unwesentlich schneller ist als die obige Kurzlösung.

bool isSubset = true;
foreach (var element in t2) {
    if (!t1.Contains(element)) {
        isSubset = false;
        break;
    }
}

Ich habe eine rudimentäre Leistungsanalyse aller Lösungen durchgeführt, und die Ergebnisse sind drastisch. Diese beiden Lösungen sind etwa 100-mal schneller als die Lösungen .Except () und .Intersect () und verwenden keinen zusätzlichen Speicher.

user2325458
quelle
Genau das !t2.Except(t1).Any()macht es. Linq arbeitet hin und her. Any()fragt ein, IEnumerableob es mindestens ein Element gibt. In diesem Szenario t2.Except(t1)wird nur das erste Element ausgegeben, von t2dem nicht vorhanden ist t1. Wenn das erste Element t2ist nicht in t1es am schnellsten beendet, wenn alle Elemente t2sind in t1dem längsten läuft.
Bis
Während ich mit einer Art Benchmark herumspielte, fand ich heraus, dass Sie beim Nehmen von t1={1,2,3,...9999}und t2={9999,9998,99997...9000}die folgenden Messungen erhalten : !t2.Except(t1).Any(): 1ms -> t2.All(e => t1.Contains(e)): 702ms. Und es wird schlimmer, je größer die Reichweite ist.
Bis
2
So funktioniert Linq nicht. t2.Except (t1)kehrt ein IEnumerablenicht ein Collection. Es werden nur dann alle möglichen Elemente ausgegeben, wenn Sie vollständig darüber iterieren, z. B. durch ToArray ()oder ToList ()oder verwenden, foreachohne das Innere zu beschädigen. Suchen Sie nach einer verzögerten Ausführung von linq , um mehr über dieses Konzept zu erfahren .
Bis
1
Ich bin mir völlig bewusst, wie die verzögerte Ausführung in Linq funktioniert. Sie können die Ausführung nach Belieben verschieben. Wenn Sie jedoch feststellen möchten, ob t2 eine Teilmenge von t1 ist, müssen Sie die gesamte Liste durchlaufen, um dies herauszufinden. Daran führt kein Weg vorbei.
user2325458
2
Nehmen wir das Beispiel aus Ihrem Kommentar t2={1,2,3,4,5,6,7,8} t1={2,4,6,8} t2.Except(t1)=> erstes Element von t2 = 1 => Differenz von 1 zu t1 ist 1 (geprüft gegen {2,4,6,8}) => Except()emittiert erstes Element 1 => Any()erhält ein Element => Any()ergibt true => keine weitere Überprüfung der Elemente in t2.
Bis
6

@ Camerons Lösung als Erweiterungsmethode:

public static bool IsSubsetOf<T>(this IEnumerable<T> a, IEnumerable<T> b)
{
    return !a.Except(b).Any();
}

Verwendung:

bool isSubset = t2.IsSubsetOf(t1);

(Dies ist ähnlich, aber nicht ganz das gleiche wie das, das auf @ Michaels Blog gepostet wurde.)

Neil
quelle
0

Aufbauend auf den Antworten von @Cameron und @Neil habe ich eine Erweiterungsmethode geschrieben, die dieselbe Terminologie wie die Enumerable-Klasse verwendet.

/// <summary>
/// Determines whether a sequence contains the specified elements by using the default equality comparer.
/// </summary>
/// <typeparam name="TSource">The type of the elements of source.</typeparam>
/// <param name="source">A sequence in which to locate the values.</param>
/// <param name="values">The values to locate in the sequence.</param>
/// <returns>true if the source sequence contains elements that have the specified values; otherwise, false.</returns>
public static bool ContainsAll<TSource>(this IEnumerable<TSource> source, IEnumerable<TSource> values)
{
    return !values.Except(source).Any();
}
sclarke81
quelle
0

Hier prüfen wir, ob in der untergeordneten t2Liste (dh t1) ein Element vorhanden ist, das nicht in der übergeordneten Liste enthalten ist (dh ). Wenn keines vorhanden ist, ist die Liste eine Teilmenge der anderen

z.B:

bool isSubset = !(t2.Any(x => !t1.Contains(x)));
Luzifer
quelle
-1

Versuche dies

static bool IsSubSet<A>(A[] set, A[] toCheck) {
  return set.Length == (toCheck.Intersect(set)).Count();
}

Die Idee hier ist, dass Intersect nur die Werte zurückgibt, die sich in beiden Arrays befinden. Wenn zu diesem Zeitpunkt die Länge der resultierenden Menge mit der ursprünglichen Menge übereinstimmt, befinden sich alle Elemente in "Menge" ebenfalls in "Prüfung", und daher ist "Menge" eine Teilmenge von "toCheck".

Hinweis: Meine Lösung funktioniert nicht, wenn "set" Duplikate enthält. Ich ändere es nicht, weil ich nicht die Stimmen anderer Leute stehlen will.

Hinweis: Ich habe für Camerons Antwort gestimmt.

JaredPar
quelle
4
Dies funktioniert, wenn es sich tatsächlich um Mengen handelt, aber nicht, wenn die zweite "Menge" wiederholte Elemente enthält, da es sich tatsächlich um eine Liste handelt. Möglicherweise möchten Sie HashSet <double> verwenden, um sicherzustellen, dass die Semantik festgelegt wurde.
Tvanfosson
funktioniert nicht, wenn beide Arrays Elemente haben, die sich nicht im anderen Array befinden.
da_berni