LINQ列表包含另一个列表（连续）

我无法找到有效但简单的方法来检查列表是否包含另一个列表（保留顺序）。它类似于string.Contains（字符串）功能。LINQ列表包含另一个列表（连续）

说我有整数四个类别：

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

来源

2012-05-24 hehewaffles

你有多少物品？（也就是说，效率至关重要，还是只是想要效率不是很低的东西？） – Ryan

它不足以满足效率要求，但它会很好 – hehewaffles

http://stackoverflow.com/questions/3529727/how-to-find-index-of-sublist-in-list – Ryan

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-25 05:34:54

仍然O（N^2），但我很喜欢这一个 – hehewaffles

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

有点少“klugy”，至少避免了很长很长列出了一些工作。

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-24 23:20:40

这似乎非常klugy，但它的工作，谢谢 – hehewaffles

如果你想少于这个，使用'.ToArray（）'在你的列表，然后使用类似的算法String.Contains（）;） –

-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-24 23:34:31 OmegaMan

尝试'var第四=新列表（）{5，2};'你的方法返回'true'，当我希望它返回'false'（顺序很重要）。 – hehewaffles

@hehewaffles完成请参阅示例。只需将索引放入KVP的容器中即可。 – OmegaMan

它仍然只测试序列的开始。例如，应该在'{1,2,3,4,5}'中找到'{2,3}'。 –

这个版本使用队列来存储可能的序列。它只会从最初的Take()开始一次迭代haystack，并且一旦找到匹配就停止迭代。但是，它在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-25 15:01:09

LINQ列表包含另一个列表（连续）

回答

相关问题