How to check if a list contains another list in the same order

Question

Is there an easy way in C # to check if a list consists of another list ?. Here is an example, I have:

var list1 = new List<int>() {1, 2, 3, 4, 5, 6,}; and the second var list2 = new List<int>() {5, 6};

this list is part of the first list, so it should return true.

var list1 = new List<int>() {1, 2, 3, 4, 5, 6,}; as well as var list3 = new List<int>() {1, 3}; should return false.

This is not a check to see if all the items in the first list in the second list exist, and also about the order. He must have the same order.

Answer 1

This works for me:

 public bool ContainsSubsequence<T>(List<T> sequence, List<T> subsequence) { return Enumerable .Range(0, sequence.Count - subsequence.Count + 1) .Any(n => sequence.Skip(n).Take(subsequence.Count).SequenceEqual(subsequence)); } 

This code uses Enumerable.Range to execute every possible starting point within the sequence , which can be the same as subsequence , and checks if the sequence segment is the same size as the subsequence at this position is actually equal to subsequence .

So for this code:

 var list1 = new List<int>() { 1, 2, 3, 4, 5, 6, }; var list2 = new List<int>() { 5, 6, }; var list3 = new List<int>() { 1, 3, }; Console.WriteLine(ContainsSubsequence(list1, list2)); Console.WriteLine(ContainsSubsequence(list1, list3)); 

I get:

 True False 

Answer 2

Thanks to @GeorgeVovos and @Enigmativity for pointing out problems in the first solution.

 public static bool HasSubSequence(List<int> main, List<int> query) { var startIndex = main.IndexOf(query.First()); if (main == null || query == null || startIndex < 0) return false; while (startIndex >= 0) { if (main.Count - startIndex < query.Count) return false; var nonMatch = false; for (int i = 0; i < query.Count; i++) { if (main[i + startIndex] != query[i]) { main = main.Skip(startIndex + 1).ToList(); startIndex = main.IndexOf(query.First()); nonMatch = true; break; } } if (!nonMatch) return true; } return false; } 

Example

 var l1 = new List<int> { 1, 2, 3, 4, 5 }; var l2 = new List<int> { 4, 5 }; var l3 = new List<int> { 1, 3 }; var l4 = new List<int> { 5, 6 }; var l5 = new List<int> { 1, 2, 3, 2, 5, 6, 2, 4, 8 }; var l6 = new List<int> { 2, 4 }; var test1 = HasSubSequence(l1, l2); //true var test2 = HasSubSequence(l1, l3); //false var test3 = HasSubSequence(l1, l4); //false var test5 = HasSubSequence(l5, l6); //true