Check if one list contains all items from another list in order

Question

How can I determine if List A contains all of the elements from List B in the same order?

List A can have additional elements that List B does not have, but must contain all elements of List B in the order that List B has them.

Example 1 (List A ending with ..., 4, 0, 6):

List A:    List B:
5          2
9          3
2          4
3
4
0
6

This should return True.

Example 2 (List A ending with ..., 0, 4, 6):

List A:    List B:
5          2
9          3
2          4
3
0
4
6

This should return False.

I found this answer from JonSkeet to see if List A contains all elements from List B however, that does not require them to be in the same order.

Not only the order doesn't matter in J.Skeets answer but also the count. So `{1,2,2,3}` and `{1,2,3}` would return `true` with `Enumerable.Except` since it is a set method which eliminates duplicates. — Tim Schmelter, Aug 03 '13 at 22:42

Tim Schmelter · Answer 1 · 2013-08-03T22:14:04.460

4

This takes each part of ListA and compares it with ListB with SequenceEqual:

bool containsSameSequence = ListA
    .Where((item, index) => index <= ListA.Count - ListB.Count)
    .Select((item, index) => ListA.Skip(index).Take(ListB.Count))
    .Any(part => part.SequenceEqual(ListB));

Demo

It returns true on the first matching sequence.

edited Aug 03 '13 at 22:14

answered Aug 03 '13 at 22:03

Tim Schmelter

450,073
74
686
939

Both your's and Eren's solutions work. However, Eren's seems to be slightly faster (and easier to read), demo using strings here: http://ideone.com/zywMpv – Ricketts Aug 03 '13 at 23:28
@Ricketts: No problem. However, the sample data is not very meaningful since you are generating the same sequence for both lists(`ListA` has just more elements), so the first test will always succeed. Since both approaches are actually the same with different syntax i assume that both will have similar performance. – Tim Schmelter Aug 03 '13 at 23:44
@Ricketts: Also, you have not used my code with the `Where` which is the Linq version of Eren's shortened `for`-loop. That's the reason for the performance difference. – Tim Schmelter Aug 03 '13 at 23:58
You are correct about my tests, check the updated version: http://ideone.com/zywMpv – Ricketts Aug 04 '13 at 00:07

Eren Ersönmez · Accepted Answer · 2013-08-03T23:15:58.333

Here's a quick way:

var equal = listA.Count - listB.Count < 0 
    ? false 
    : Enumerable.Range(0, listA.Count - listB.Count).Any(i => 
      listA.Skip(i).Take(listB.Count).SequenceEqual(listB));

However, I'd prefer to use an extension method like this:

public static bool ContainsSequence<T>(this IEnumerable<T> outer, 
                                       IEnumerable<T> inner)
{
    var innerCount = inner.Count();
    for(int i = 0; i < outer.Count() - innerCount; i++)
    {
        if(outer.Skip(i).Take(innerCount).SequenceEqual(inner))
            return true;
    }

    return false;
 }

which you can call like:

var equals = listA.ContainsSequence(listB);

And here's a more efficient version of the same extension method specific to List<T>:

public static bool ContainsSequence<T>(this List<T> outer, List<T> inner)
{
    var innerCount = inner.Count;

    for (int i = 0; i < outer.Count - innerCount; i++)
    {
        bool isMatch = true;
        for (int x = 0; x < innerCount; x++)
        {
            if (!outer[i + x].Equals(inner[x]))
            {
                isMatch = false;
                break;
            }
        }

        if (isMatch) return true;
    }

    return false;
}

Does not work if duplicates should matter,Intersect eliminates duplicates. — Tim Schmelter, Aug 03 '13 at 21:52
Thanks for the solution. Your's is slightly faster than Tim's. — Ricketts, Aug 03 '13 at 23:28
@Ricketts Thank you. But normally, the last method I provided should be faster. Your test data is a bit biased since the match is always at the beginning. For example, add another set of "B"s before "A"s in ListA, and you should find my List specific method is faster. — Eren Ersönmez, Aug 03 '13 at 23:52

score 1 · Answer 3 · answered Aug 03 '13 at 23:06

1

Use String.Join() to concat ListA elements together. Then use it again to concat ListB elements together. Then use ConcatListA.IndexOf(ConcatListB).

answered Aug 03 '13 at 23:06

dotNET

33,414
24
162
251

score 0 · Answer 4 · edited Nov 24 '20 at 02:34

I think my version is more efficient.

public static class CollectionExtension
{
    public static bool SequenceContain<T>(this IEnumerable<T> target, IEnumerable<T> that)
    {
        var targetEnumerater = target.GetEnumerator();
        var thatEnumerater = that.GetEnumerator();
        var thatHasValue = thatEnumerater.MoveNext();
        var targetHasValue = targetEnumerater.MoveNext();
        var matchCount = 0;
        try
        {
            while (thatHasValue && targetHasValue)
            {
                if (!EqualityComparer<T>.Default.Equals(targetEnumerater.Current, thatEnumerater.Current))
                {
                    if (matchCount > 0)
                    {
                        thatEnumerater.Reset();
                        thatEnumerater.MoveNext();
                        matchCount = 0;
                    }
                    targetHasValue = targetEnumerater.MoveNext();
                    continue;
                }
                targetHasValue = targetEnumerater.MoveNext();
                thatHasValue = thatEnumerater.MoveNext();
                matchCount++;
            }
            return matchCount == that.Count();
        }
        finally
        {
            thatEnumerater.Dispose();
            targetEnumerater.Dispose();
        }
    }
}

Check if one list contains all items from another list in order

4 Answers4

Linked