How to check if list contains another list in same order

Question

Is there any simple way in c# to check if list consist of another list?. Here is example, I have:

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

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

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

It's not about checking if all elements in first list exist in second list but also about order. It has to have the same order.

What have you tried? What code have you written? What research have you performed? — nicomp, Jan 03 '16 at 10:08
I would have been good if your question contained valid code to work from. — Enigmativity, Jan 03 '16 at 10:10
Yes for now i need it just for intigers. For now i was trying to find if already there is any existing solution for this problem. And yes order is important — wgrzesiak147, Jan 03 '16 at 10:11
_"For now i was trying to find if already there is any existing solution for this problem"_ - but "C# find list in list" (or "C# test collection contains sequence") yields thousands of web search results. What have you tried? — CodeCaster, Jan 03 '16 at 10:20
See [Check if one list contains all items from another list in order](http://stackoverflow.com/questions/18037625/check-if-one-list-contains-all-items-from-another-list-in-order). — CodeCaster, Jan 03 '16 at 10:38
@dotctor - The `,` at the end of each of my lists in my answer were intended. I have rolled-back your edit. — Enigmativity, Jan 03 '16 at 10:46

Enigmativity · Accepted Answer · 2016-01-03T10:45:33.807

13

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 run through every possible starting point within sequence that could be the same as subsequence, and checks if the segment of sequence the same size as 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

edited Jan 03 '16 at 10:45

answered Jan 03 '16 at 10:16

Enigmativity

113,464
11
89
172

With `var list3 = new List() { 1, 2, };` it should returns `true` but it returns `false`! – Salah Akbari Jan 03 '16 at 10:24
@user2946329 - I did have an error in the code, but I fixed it. `{ 1, 2 }` works fine now. – Enigmativity Jan 03 '16 at 10:29
@Enigmativity .. Yes. Now it became a good and comprehensive solution. +1. – Salah Akbari Jan 03 '16 at 10:34
I tested this a litle bit and it throws an exception if sequence.Count is less than subsequence.Count. So it's quite necessary to add "if" condition at the begining of this method. – wgrzesiak147 Jan 03 '16 at 15:21
@wgrzesiak147 - Yes, that's fair enough. I wrote the code for brevity, not robustness. I generally assume that it's easy to see the intent of the code if it is kept as simple as possible. But I do believe the most coders would understand the need to fortify the code. – Enigmativity Jan 03 '16 at 22:40
I have no idea what the code means, but it works, and looks like magic. so i like it. – Pingi Mar 21 '18 at 01:04

Arghya C · Answer 2 · 2016-01-03T11:00:06.063

Thanks @GeorgeVovos & @Enigmativity for pointing out the issues in 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

You need to wrap your code with a while loop (and modify indexof a little) because the first element of the second list might exists before — George Vovos, Jan 03 '16 at 10:34
This still doesn't work if `query.First()` appears in `main` before the subsequence. — Enigmativity, Jan 03 '16 at 10:35
Indeed,the for loop has to change also.the list my not appear at the start — George Vovos, Jan 03 '16 at 10:38

How to check if list contains another list in same order

2 Answers2

Linked

Related