In C#, What is the best way to see if a list contains another list?

Question

If i have a list of strings, what is the best way to determine if every element in another list is contains in this list. For example:

List<string> list = new List<string>();
list.Add("Dog");
list.Add("Cat");
list.Add("Bird");

List<string> list2 = new List<string>();
list.Add("Dog");
list.Add("Cat");

if (list.ContainsList(list2))
{
      Console.Write("All items in list2 are in list1")
}

I am trying to determine if there something like this "ContainsList" method?

Good discussion here on this http://stackoverflow.com/questions/332973/linq-check-whether-an-array-is-a-subset-of-another @leora — ojhawkins, Oct 29 '13 at 01:08

score 6 · Accepted Answer · answered Oct 29 '13 at 00:48

6

if (!list2.Except(list).Any())

answered Oct 29 '13 at 00:48

SLaks

868,454
176
1,908
1,964

Ilya Ivanov · Answer 2 · 2013-10-29T01:31:54.513

Loved SLaks version. Just for completeness, you can use HashSet method IsSubsetOf when performing set operations (also check IsSupersetOf method). There are pros and cons for this approach. Next code shows an example:

var list1 = new HashSet<string>{ "Dog", "Cat", "Bird" };

var list2 = new HashSet<string>{ "Dog", "Cat" };

if (list2.IsSubsetOf(list1))
{
      Console.Write("All items in list2 are in list1");
}

Except method is streaming in nature. In query list2.Except(list1) list1 is buffered completely into memory, and you iterate one item at a time through list2. IsSubsetOf works eagerly in the opposite manner. This starts to make a difference when you have huge sets of data.

To analyse the worst case performance, here is some code from Except implementation at Monos Enumerable (dotPeek gives very similar results, just less readable)

var items = new HashSet<TSource> (second, comparer);  //list1.Count

foreach (var element in first)                        //list2.Count
    if (items.Add (element))                          //constant time
        yield return element;

as result O(list1.Count + list2.Count), loops aren't nested.

IsSubset has next method call, if second IEnumerable is HashSet (decompiled via dotPeek):

private bool IsSubsetOfHashSetWithSameEC(HashSet<T> other)
{
    foreach (T obj in this)         //list2.Count
        if (!other.Contains(obj))   //constant time
            return false;

    return true;
}

Resulting in O(list2.Count) if list1 is a HashSet.

Using Linq's `Except()` is an O(mn) operation, I believe, whilst `HashSet.IsSubsetOf()` is O(n). — Nicholas Carey, Oct 29 '13 at 01:06
@NicholasCarey well, depends on definitions. `Except` takes two `IEnumerable`s, construct `HashSet` from right and iterates over left calling `Add` method on `HashSet`. This gives `m + n`, as far as I can see. `Add` method takes constant time. `IsSubset` has this line `HashSet hashSet = other as HashSet;` which makes a huge difference removing the need to construct `HashSet` from `list1`. Then it left only with `O(n)` indeed, where n = `list1.Count`. — Ilya Ivanov, Oct 29 '13 at 01:11
@NicholasCarey `Enumerable.Except` actually creates a temporary hash table during enumeration. That makes it O(n+m), not O(nm). — Sedat Kapanoglu, Oct 29 '13 at 01:14

score 0 · Answer 3 · answered Oct 29 '13 at 01:08

0

How about,

var list1 = new List<string>{"Dog","Cat","Bird"};
var list2 = new List<string>{"Dog","Cat"};

if (list1.Union(list2).SequenceEqual(list1))
    Console.Write("All items in list2 are in list1");

answered Oct 29 '13 at 01:08

spinalfrontier

567
1
10
20

praga2050 · Answer 4 · 2013-10-29T04:42:09.310

0

How about this

list1.intersect (list2).ToList ().Foreach ((x)=>
{
Console.Writeline (x)
});

edited Oct 29 '13 at 04:42

answered Oct 29 '13 at 02:52

praga2050

729
9
18

In C#, What is the best way to see if a list contains another list?

4 Answers4