检查一个列表是否按顺序包含另一个列表的所有项目

Question

如何确定List A是否按照与List B相同的顺序包含所有元素？

List A可以有List B没有的其他元素，但必须按照List B的顺序包含所有List B的元素。

---

示例1（List A以..., 4, 0, 6结尾）：

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

这应该返回True。

---

示例2（List A以..., 0, 4, 6结尾）：

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

应该返回False。

---

我找到了JonSkeet的答案，用于检查List A是否包含来自List B的所有元素，但是这并不要求它们按相同的顺序排列。

- Ricketts

---

在J.Skeets的答案中，顺序不仅不重要，计数也不重要。因此，由于Enumerable.Except是一种消除重复项的集合方法，所以{1,2,2,3}和{1,2,3}将返回true。 - Tim Schmelter

Answer 1

这段代码使用SequenceEqual将ListA的每个部分与ListB进行比较：

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));

演示

在第一个匹配序列时它会返回true。

- Tim Schmelter

---

你和Eren的解决方案都可以工作。然而，Eren的似乎稍微快一些（并且更易于阅读），这里使用字符串进行演示：http://ideone.com/zywMpv - Ricketts

@Ricketts：没问题。然而，样本数据并不是很有意义，因为您为两个列表生成了相同的序列（ListA只是具有更多元素），因此第一个测试将始终成功。由于这两种方法实际上是相同的，只是语法不同，我认为它们的性能都会相似。 - Tim Schmelter

@Ricketts：另外，你没有使用我的代码中的Where，这是Linq版本的Eren缩短的for循环。这就是性能差异的原因。 - Tim Schmelter

你关于我的测试是正确的，请检查更新版本：http://ideone.com/zywMpv - Ricketts

Answer 2

这里有一种快速方法：

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));

---

然而，我更倾向于使用类似这样的扩展方法：

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;
 }

您可以像这样调用:

var equals = listA.ContainsSequence(listB);

---

以下是同一扩展方法的更加高效版本，特定于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;
}

- Eren Ersönmez

---

如果重复项很重要，那么它不起作用。而Intersect则会消除重复项。 - Tim Schmelter

@TimSchmelter 也提供了一个解决重复项的方案。 - Eren Ersönmez

感谢提供的解决方案。您的比Tim的稍微快一些。 - Ricketts

@Ricketts 谢谢。但通常来说，我提供的最后一种方法应该更快。你的测试数据有点偏见，因为匹配总是在开头。例如，在ListA中再添加一组“B”在“A”之前，你会发现我的List<T>特定方法更快。 - Eren Ersönmez

Answer 3

使用String.Join()将ListA元素连接在一起。然后再次使用它将ListB元素连接在一起。然后使用ConcatListA.IndexOf(ConcatListB)。

- dotNET

Answer 4

我认为我的版本更高效。

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();
        }
    }
}

- Sean