2

我很难找到一种有效但简单的方法来检查列表是否包含另一个列表（保留顺序）。它类似于 string.Contains(string) 功能。

假设我有四个整数集合：

 A = [1, 2, 3, 4, 5]
 B = [2, 3]
 C = [5, 6, 7]
 D = [3, 2, 4]

A.Contains(B)会是真的，而A.Contains(C)和A.Contains(D)会是假的。

如果可以提供帮助，我宁愿不使用迭代器，但我无法想象一种有效的方法。以下代码效率极低。

 public static bool IsSequentiallyEqual<T>(this IEnumerable<T> lhs, IEnumerable<T> rhs)
 {
      return lhs.Zip(rhs, (a, b) => a.Equals(b)).All(isEqual => isEqual == true);
 }

 public static bool StartsWith<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
 {
      return haystack.Take(needle.Count()).IsSequentiallyEqual(needle);
 }

 public static bool Contains<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
 {
      var result = list.SkipWhile((ele, index) => haystack.Skip(index).StartsWith(needle));
      return result.Count() >= needle.Count();
 }
4

4 回答 4

2 
public static bool Contains<T>(this IEnumerable<T> first, IEnumerable<T> second)
 {
      return string.Join("~", first).Contains(string.Join("~", second));
 }

少一点“笨拙”，至少避免为长长的列表做一些工作。

public static bool Contains<T>(this IEnumerable<T> first, IEnumerable<T> second)
   {
       //trying to avoid multiple enumeration
        var firstList = first.ToList();
        var secondList = second.ToList();

        if (!secondList.Any(firstList.Contains)) return false;
        if (secondList.Count() > firstList.Count()) return false;
        if (Math.Max(firstList.Count(), secondList.Count()) > 99999)
             throw new ShouldNotUseThisUglyMethodException("I'm too kludgy to be used. Let me die...");
        return string.Join("~", firstList).Contains(string.Join("~", secondList));
    }
于 2012-05-24T23:20:40.967 回答
1 
public static bool Contains<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
{
    var hayList = haystack.ToList();
    var needleList = needle.ToList();
    return Enumerable.Range(0, hayList.Count)
                     .Select(start => hayList.Skip(start).Take(needleList.Count))
                     .Any( subsequence => subsequence.SequenceEqual(needleList));
}
于 2012-05-25T05:34:54.753 回答
0

此版本使用队列来存储可能的子序列。haystack除了初始之外，它只Take()迭代一次，一旦找到匹配项，它就会停止迭代。但是，它会改变 LINQ 语句中的变量。

public static bool Contains<T>(this IEnumerable<T> haystack, IEnumerable<T> needle)
{
    var needleList = needle.ToList();
    var queue = new Queue<T>(haystack.Take(needleList.Count - 1));
    return haystack.Skip(needleList.Count - 1)
                   .Any( hay =>   
                       {
                           queue.Enqueue(hay);
                           bool areEqual = queue.SequenceEqual(needleList);
                           queue.Dequeue();
                           return areEqual;
                       });  
}
于 2012-05-25T15:01:09.337 回答
-1

使用哈希的工作。请注意，可以进行一些检查以立即返回错误，但我只展示了该过程的实质。这是方便的扩展格式：

更新为处理订单

void Main()
{
    var first        = new List<int>() { 1, 2, 5 };
    var firstInOrder = new List<int>() { 1, 2, 3 };
    var second       = new List<int>() { 1, 2, 3, 4, 5 };
    var third        = new List<int>() { 1, 10, 20 };

    Console.WriteLine( first.FoundInOther( second ) );        // False
    Console.WriteLine( firstInOrder.FoundInOther( second ) ); // True
    Console.WriteLine( first.FoundInOther( third ) );         // False

}

public static class NumberExtensions
{

    public static bool FoundInOther( this IEnumerable<int> initial, IEnumerable<int> other )
    {
        int index = -1;
        var asDictionary = other.ToDictionary( itm => itm, itm => ++index );

        index = -1;
        return initial.All( oth => asDictionary.ContainsKey( oth ) && (asDictionary[oth] == ++index));
    }

}
于 2012-05-24T23:34:31.857 回答