0

Is it possible using LINQ to test for a match of a sequence of list items? e.g.

var masterList = new List<string>{"fox", "jumps", "dog"};
var childList1 = new List<string>{"fox", "jumps"};
var childList2 = new List<string>{"fox", "dog"};

I'd like to write something such that looking for childList1 in masterList is true, but childList2 is false, because there's something in between.

EDIT: {"jumps", "dog"} would also match.

wonea
  • 4,783
  • 17
  • 86
  • 139
user888734
  • 3,797
  • 5
  • 36
  • 67
  • Little round about, but if [`Intersect`](http://msdn.microsoft.com/en-us/library/bb546153.aspx) of both lists is equal to the child list length, then it is contained in the master list. – KyleMit Sep 06 '13 at 21:36
  • @KyleMit Intersect isn't too awesome here because it will produce a new `IEnumberable` you could then check that it is the same as the childList, but it's not really ideal. You end up where you started if it is a subset. – evanmcdonnal Sep 06 '13 at 21:38
  • Does it have to match _any_ sequence or do they both have to _start_ with the same values? Meaning would `{"jumps", "dog"}` match, too? – D Stanley Sep 06 '13 at 21:39
  • Yes, {"jumps", "dog"} should also be a match. – user888734 Sep 06 '13 at 21:44
  • Would `{"fox", "dog"};` not be a match since there is a value between fox and dog in master? – evanmcdonnal Sep 06 '13 at 21:51

3 Answers3

1

If exact sequence of elements is important try something like:

public static bool ListContains<T>(List<T> source, List<T> search)
{
    if (search.Count > source.Count)
        return false;

    return Enumerable.Range(0, source.Count - search.Count + 1)
        .Select(a => source.Skip(a).Take(search.Count))
        .Any(a => a.SequenceEqual(search));
}

public static void Main(string[] args)
{
    var masterList = new List<string> { "fox", "jumps", "dog" };
    var childList1 = new List<string> { "fox", "jumps" };
    var childList2 = new List<string> { "fox", "dog" };

    Console.WriteLine(ListContains(masterList, childList1));
    Console.WriteLine(ListContains(masterList, childList2));
}
Andrei
  • 1,015
  • 1
  • 11
  • 19
1

My answer is similar to Andrei's but may be faster since it looks for the first item in the parent list to limit the number of searches:

public bool SubsequenceEquals<T>(IEnumerable<T> masterList, IEnumerable<T> childList)
{
    // find all indexes 
    var matches = masterList.Select((s, i) => new {s, i})
                            .Where(m => m.s.Equals(childList.First()))
                            .Select (m => m.i);

    return matches.Any(m => Enumerable.SequenceEqual(childList, masterList
                                                           .Skip(m)
                                                           .Take(childList.Count())));
}
wonea
  • 4,783
  • 17
  • 86
  • 139
D Stanley
  • 149,601
  • 11
  • 178
  • 240
  • This won't be faster (is likely to be about 50% slower I would say) because it will have to iterate the master list twice (up to the first occurrence of the first element from childlist, plus it will need to call `childList.First()` for every iteration. And I personally also don't like creating temporary objects unnecessarily. All this is unnecessary because SequenceEquals stops iterating both sequences as soon as it hits first mismatch. – Andrei Sep 09 '13 at 13:19
0

There is another question that has a working answer; Check whether an array is a subset of another

bool isSubest = !childList1.Except(masterList).Any();

will do it for you. You could also do 

  if (childList1.Except(masterList).Count > 0)
      // items in child not in master
  else
       //child is a subest of master
Community
  • 1
  • 1
evanmcdonnal
  • 46,131
  • 16
  • 104
  • 115