Sprawdź, czy tablica jest podzbiorem innej


145

Masz pomysł, jak sprawdzić, czy ta lista jest podzbiorem innej listy?

W szczególności mam

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

Jak sprawdzić, czy t2 jest podzbiorem t1, używając LINQ?


Jeśli listy są posortowane (jak w twoim przykładzie), powinno to być możliwe w czasie O (n + m).
Panik pułkownik

Odpowiedzi:


255
bool isSubset = !t2.Except(t1).Any();


@Bul Ikana Działanie tego kodu jest proste, metoda rozszerzenia wywołuje wewnętrznie Equals i GetHashCode metod przesłoniętych klas obiektów, jeśli nie ma elementu IEqualityComparer dla tego zadania.
Mrinal Kamboj

2
Jeśli listy mają długość n i m, jaka jest złożoność czasowa tego algorytmu?
Panik pułkownik

2
Byłoby miło, gdyby sprowadzono to do metody linq o nazwie ContainsAll
Sebastian Patten

60

Jeśli pracujesz z zestawami, użyj HashSet zamiast List. Następnie możesz po prostu użyć IsSubsetOf ()

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

bool isSubset = t2.IsSubsetOf(t1);

Przepraszamy, że nie używa LINQ. :-(

Jeśli musisz używać list, rozwiązanie @ Jareda działa z zastrzeżeniem, że będziesz musiał usunąć wszelkie powtarzające się elementy, które istnieją.


3
Dokładnie. Chcesz operacji na zbiorach, użyj klasy przeznaczonej dla nich. Rozwiązanie Camerona jest kreatywne, ale nie tak przejrzyste / wyraziste jak zestaw HashSet.
technophile

2
Nie zgadzam się, ponieważ pytanie konkretnie mówi „użyj LINQ”.
JaredPar

9
@JaredPar: I co z tego? Czy nie lepiej jest pokazać komuś właściwą drogę niż drogę, którą chce iść?
Jonathan Allen

Lista zachowuje swoją kolejność, ale zestaw nie. Jeśli kolejność jest ważna, dałoby to nieprawidłowe wyniki.
UuDdLrLrSs

11

Jeśli wykonujesz testy jednostkowe , możesz również użyć metody CollectionAssert.IsSubsetOf :

CollectionAssert.IsSubsetOf(subset, superset);

W powyższym przypadku oznaczałoby to:

CollectionAssert.IsSubsetOf(t2, t1);

7

Jest to znacznie wydajniejsze rozwiązanie niż inne zamieszczone tutaj, zwłaszcza najlepsze rozwiązanie:

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

Jeśli możesz znaleźć pojedynczy element w t2, który nie jest w t1, to wiesz, że t2 nie jest podzbiorem t1. Zaletą tej metody jest to, że wszystko odbywa się na miejscu, bez przydzielania dodatkowej przestrzeni, w przeciwieństwie do rozwiązań wykorzystujących .Except lub .Intersect. Co więcej, to rozwiązanie może się zepsuć, gdy tylko znajdzie pojedynczy element, który narusza warunek podzbioru, podczas gdy inne kontynuują wyszukiwanie. Poniżej znajduje się optymalna długa forma rozwiązania, która w moich testach jest tylko nieznacznie szybsza niż powyższe rozwiązanie skrócone.

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

Przeprowadziłem podstawową analizę wydajności wszystkich rozwiązań, a wyniki są drastyczne. Te dwa rozwiązania są około 100 razy szybsze niż rozwiązania .Except () i .Intersect () i nie wymagają dodatkowej pamięci.


To jest dokładnie to, co !t2.Except(t1).Any()robi. Linq pracuje w tę iz powrotem. Any()pyta, IEnumerableczy jest co najmniej jeden element. W tym scenariuszu t2.Except(t1)emituje tylko pierwszy element, t2którego nie ma t1. Jeśli pierwszego elementu t2nie t1ma, kończy się najszybciej, jeśli wszystkie elementy t2są w t1nim, działa najdłużej.
abto

Podczas zabawy z jakiegoś wzorca, I okazało się, jeśli wziąć t1={1,2,3,...9999}i t2={9999,9998,99997...9000}, można uzyskać następujące pomiary: !t2.Except(t1).Any(): 1ms -> t2.All(e => t1.Contains(e)): 702ms. Im większy zakres, tym gorzej.
abto

2
To nie jest sposób, w jaki działa Linq. t2.Except (t1)zwraca a IEnumerablenot a Collection. Emituje wszystkie możliwe elementy tylko wtedy, gdy całkowicie go iterujesz, na przykład przez ToArray ()lub ToList ()lub używasz foreachbez włamywania się do środka. Wyszukaj linq odroczone wykonanie, aby przeczytać więcej o tej koncepcji.
abto

1
Jestem w pełni świadomy tego, jak działa odroczone wykonanie w Linq. Możesz odroczyć wykonanie, ile chcesz, ale jeśli chcesz określić, czy t2 jest podzbiorem t1, musisz powtórzyć całą listę, aby to rozgryźć. Tego faktu nie da się obejść.
user2325458

2
Weźmy przykład z twojego komentarza t2={1,2,3,4,5,6,7,8} t1={2,4,6,8} t2.Except(t1)=> pierwszy element t2 = 1 => różnica od 1 do t1 wynosi 1 (sprawdzane względem {2,4,6,8}) => Except()emituje pierwszy element 1 => Any()pobiera element => Any()daje w wyniku true => brak dalszego sprawdzania elementów w t2.
abto

6

Rozwiązanie @ Camerona jako metoda rozszerzenia:

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

Stosowanie:

bool isSubset = t2.IsSubsetOf(t1);

(Jest podobny, ale nie taki sam jak ten opublikowany na blogu @ Michael)


0

Opierając się na odpowiedziach z @Cameron i @Neil, napisałem metodę rozszerzającą, która używa tej samej terminologii, co klasa Enumerable.

/// <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();
}

0

Tutaj sprawdzamy, czy istnieje element na liście podrzędnej (tj. t2), Który nie jest zawarty w liście nadrzędnej (tj. t1) .Jeśli taki nie istnieje, to lista jest podzbiorem drugiego

na przykład:

bool isSubset = !(t2.Any(x => !t1.Contains(x)));

-1

Spróbuj tego

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

Pomysł polega na tym, że Intersect zwróci tylko wartości znajdujące się w obu tablicach. W tym momencie, jeśli długość wynikowego zestawu jest taka sama jak oryginalnego zestawu, to wszystkie elementy w „zestawie” są również w „check” i dlatego „set” jest podzbiorem „toCheck”

Uwaga: moje rozwiązanie nie działa, jeśli „zestaw” ma duplikaty. Nie zmieniam tego, ponieważ nie chcę kraść głosów innych ludzi.

Podpowiedź: głosowałem za odpowiedzią Camerona.


4
Działa to, jeśli rzeczywiście są zbiorami, ale nie wtedy, gdy drugi „zestaw” zawiera powtarzające się elementy, ponieważ tak naprawdę jest listą. Możesz chcieć użyć HashSet <double>, aby upewnić się, że ma ustawioną semantykę.
tvanfosson

nie działa, gdy obie tablice mają elementy, których nie ma w drugiej tablicy.
da_berni
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.