Check if one IEnumerable contains all elements of another IEnumerable

What is the fastest way to determine if one IEnumerable contains all the elements of another IEnumerable when comparing a field/property of each element in both collections?

public class Item
{
    public string Value;

    public Item(string value)
    {
        Value = value;
    }
}

//example usage

Item[] List1 = {new Item("1"),new Item("a")};
Item[] List2 = {new Item("a"),new Item("b"),new Item("c"),new Item("1")};

bool Contains(IEnumerable<Item> list1, IEnumerable<Item>, list2)
{
    var list1Values = list1.Select(item => item.Value);
    var list2Values = list2.Select(item => item.Value);

    return //are ALL of list1Values in list2Values?
}

Contains(List1,List2) // should return true
Contains(List2,List1) // should return false

Solution 1:

There is no "fast way" to do this unless you track and maintain some state that determines whether all values in one collection are contained in another. If you only have IEnumerable<T> to work against, I would use Intersect.

var allOfList1IsInList2 = list1.Intersect(list2).Count() == list1.Count();

The performance of this should be very reasonable, since Intersect() will enumerate over each list just once. Also, the second call to Count() will be optimal if the underlying type is an ICollection<T> rather than just an IEnumerable<T>.

Solution 2:

You could also use Except to remove from the first list all values that exist in the second list, and then check if all values have been removed:

var allOfList1IsInList2 = !list1.Except(list2).Any();

This method had the advantage of not requiring two calls to Count().

Solution 3:

C# 3.5+

Using Enumerable.All<TSource> to determine if all List2 items are contained in List1:

bool hasAll = list2Uris.All(itm2 => list1Uris.Contains(itm2));

This will also work when list1 contains even more than all the items of list2.

Solution 4:

Kent's answer is fine and short, but the solution that he provides always requires iteration over the whole first collection. Here is the source code:

public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
    if (first == null)
        throw Error.ArgumentNull("first");
    if (second == null)
        throw Error.ArgumentNull("second");
    return Enumerable.IntersectIterator<TSource>(first, second, comparer);
}

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource source in second)
        set.Add(source);
    foreach (TSource source in first)
    {
        if (set.Remove(source))
            yield return source;
    }
}

That is not always required. So, here is my solution:

public static bool Contains<T>(this IEnumerable<T> source, IEnumerable<T> subset, IEqualityComparer<T> comparer)
{
    var hashSet = new HashSet<T>(subset, comparer);
    if (hashSet.Count == 0)
    {
        return true;
    }

    foreach (var item in source)
    {
        hashSet.Remove(item);
        if (hashSet.Count == 0)
        {
            break;
        }
    }

    return hashSet.Count == 0;
}

Actually, you should think about using ISet<T> (HashSet<T>). It contains all required set methods. IsSubsetOf in your case.

Solution 5:

The solution marked as the answer would fail in the case of repetitions. If your IEnumerable only contains distinct values then it would pass.

The below answer is for 2 lists with repetitions:

        int aCount = a.Distinct().Count();
        int bCount = b.Distinct().Count();

        return aCount == bCount &&
               a.Intersect(b).Count() == aCount;