如何检查列表是否按相同顺序包含另一个列表

Question

在C#中，有没有简单的方法来检查一个列表是否包含另一个列表？以下是示例：

var list1 = new List<int>() {1, 2, 3, 4, 5, 6,}; 和第二个列表： var list2 = new List<int>() {5, 6};

这个列表是第一个列表的一部分，所以应该返回true。

var list1 = new List<int>() {1, 2, 3, 4, 5, 6,}; 和 var list3 = new List<int>() {1, 3}; 应该返回false。

它不仅检查第一个列表中的所有元素是否存在于第二个列表中，还要考虑顺序。它们必须具有相同的顺序。

- wgrzesiak147

---

你想要一个通用的解决方案还是只针对整数列表？ - Hamid Pourjam

你尝试过什么？你写了什么代码？你做了哪些研究？ - nicomp

@dotctor - 我在我的回答中每个列表末尾的,都是有意为之的。我已经撤销了你的编辑。 - Enigmativity

这是什么目的？@Enigmativity - Hamid Pourjam

@dotctor - 这是有效的语法，有助于重构。 - Enigmativity

Answer 1

这对我有效：

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

这段代码使用了Enumerable.Range来遍历sequence中每一个可能作为subsequence起点的位置，并检查该位置处与subsequence相同大小的一段sequence是否与subsequence相等。

因此，对于这段代码：

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

我得到：

True
False

- Enigmativity

---

使用 var list3 = new List<int>() { 1, 2, }; 应该返回 true，但实际上返回了 false！ - Salah Akbari

@user2946329 - 我的代码确实有错误，但我已经修复了它。{1, 2}现在可以正常工作了。 - Enigmativity

@Enigmativity .. 是的。现在它成为了一个好的、全面的解决方案。+1。 - Salah Akbari

我对此进行了一些测试，如果sequence.Count小于subsequence.Count，则会引发异常。因此，在此方法的开头添加“if”条件非常必要。 - wgrzesiak147

@wgrzesiak147 - 是的，这是公平的。我写代码时注重简洁而不是健壮性。我通常认为，如果代码尽可能简单，那么它的意图就很容易理解。但我相信大多数程序员都会明白加固代码的必要性。 - Enigmativity

我不知道这段代码的含义，但它能够正常运行，看起来就像魔法一样。所以我很喜欢它。 - Pingi

Answer 2

感谢 @GeorgeVovos 和 @Enigmativity 指出第一个解决方案中的问题。

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

示例

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

- Arghya C

---

元素的顺序很重要。 - Enigmativity

你需要用 while 循环包装你的代码（并稍微修改 indexof），因为第二个列表的第一个元素可能在之前已经存在。 - George Vovos

如果在子序列之前，query.First() 出现在 main 中，这仍然无法正常工作。 - Enigmativity

实际上，for循环也必须更改。列表可能不会出现在开头。 - George Vovos