Czy .NET ma sposób na sprawdzenie, czy lista a zawiera wszystkie elementy z listy b?

98

Mam następującą metodę:

namespace ListHelper
{
    public class ListHelper<T>
    {
        public static bool ContainsAllItems(List<T> a, List<T> b)
        {
            return b.TrueForAll(delegate(T t)
            {
                return a.Contains(t);
            });
        }
    }
}

Celem jest określenie, czy lista zawiera wszystkie elementy innej listy. Wydaje mi się, że coś takiego byłoby już wbudowane w .NET, czy tak jest i czy powielam funkcjonalność?

Edycja: przepraszam za nie stwierdzenie z góry, że używam tego kodu w wersji Mono 2.4.2.

— Matt Haley
źródło

Zobacz także stackoverflow.com/questions/332973/…

— Colonel Panic

Twój algorytm jest kwadratowy O (nm). Jeśli listy są posortowane, sprawdzenie, czy jedna jest podzbiorem drugiej, powinno być możliwe w czasie O (n + m).

— Colonel Panic

177

Jeśli używasz .NET 3.5, jest to łatwe:

public class ListHelper<T>
{
    public static bool ContainsAllItems(List<T> a, List<T> b)
    {
        return !b.Except(a).Any();
    }
}

Sprawdza, czy są jakieś elementy, bktórych nie ma a- a następnie odwraca wynik.

Zwróć uwagę, że byłoby nieco bardziej konwencjonalne uczynienie metody generycznej zamiast klasy i nie ma powodu, aby wymagać List<T>zamiast IEnumerable<T>- więc prawdopodobnie byłoby to preferowane:

public static class LinqExtras // Or whatever
{
    public static bool ContainsAllItems<T>(this IEnumerable<T> a, IEnumerable<T> b)
    {
        return !b.Except(a).Any();
    }
}

— Jon Skeet
źródło

1

To nie jest testowane, ale nie zwróci b.Except (a) .Empty (); być bardziej czytelne?

— Nils

7

Tyle że Empty () nie zwraca wartości logicznej. Zwraca IEnumerable <T> bez elementów.

— Peter Stephens

2

Uważam, że możesz użyć LINQ to Objects in Mono ... ale byłoby pomocne, gdybyś określił wymagania w pytaniu na początek. Której wersji Mono używasz?

— Jon Skeet

1

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

— Panik pułkownik

1

@ColonelPanic: Zakładając brak kolizji hash, O (n + m).

— Jon Skeet,

38

Zawarte w .NET 4: Enumerable.All

public static bool ContainsAll<T>(IEnumerable<T> source, IEnumerable<T> values)
{
    return values.All(value => source.Contains(value));
}

— Tomasz
źródło

35

Tylko dla zabawy, @ JonSkeet za odpowiedź jako metodę rozszerzenia:

/// <summary>
/// Does a list contain all values of another list?
/// </summary>
/// <remarks>Needs .NET 3.5 or greater.  Source:  https://stackoverflow.com/a/1520664/1037948 </remarks>
/// <typeparam name="T">list value type</typeparam>
/// <param name="containingList">the larger list we're checking in</param>
/// <param name="lookupList">the list to look for in the containing list</param>
/// <returns>true if it has everything</returns>
public static bool ContainsAll<T>(this IEnumerable<T> containingList, IEnumerable<T> lookupList) {
    return ! lookupList.Except(containingList).Any();
}

— drzaus
źródło

2

podobnie: zawiera Any =

public static bool ContainsAny<T>(this IEnumerable<T> haystack, IEnumerable<T> needle) { return haystack.Intersect(needle).Count() > 0; }

. Próbowałem kilku szybkich porównań wydajności haystack.Count() - 1 >= haystack.Except(needle).Count();i Intersectwydawało się, że przez większość czasu radzę sobie lepiej.

— drzaus

4

sheesh ... Any()nie używaj Count() > 0:

public static bool ContainsAny<T>(this IEnumerable<T> haystack, IEnumerable<T> needle) { return haystack.Intersect(needle).Any(); }

— drzaus

0

Możesz też użyć innego sposobu. Zastąp równa się i użyj tego

public bool ContainsAll(List<T> a,List<T> check)
{
   list l = new List<T>(check);
   foreach(T _t in a)
   {
      if(check.Contains(t))
      {
         check.Remove(t);
         if(check.Count == 0)
         {
            return true;
         }
      }
      return false;
   }
}

— user3210251
źródło

2

list l = new List<T>(check);Nie sądzę, żeby to się skompilowało, a jeśli tak, jest to całkowicie niepotrzebne, ponieważ checkjest już lista

— Rohit Vipin Mathews