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列表包含另一個列表（連續）

回答

相關問題