La liste LINQ contient une autre liste (contiguë)

Question

Je n'arrive pas à trouver un moyen efficace mais simple de vérifier si une liste contient une autre liste (ordre de conservation). C'est analogue à la chaîne. Contient (fonctionnalité).

Dire que j'ai quatre collections de ints:

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

A.Contains(B) serait vrai, alors que A.Contains(C) et A.Contains(D) serait faux.

Je préfère ne pas utiliser les itérateurs si cela peut être utile, mais je ne peux pas imaginer un moyen efficace de le faire; le code suivant est extrêmement inefficace.

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

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

Answer 2

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

Un peu moins « klugy », au moins éviter un travail pendant de longues listes longues.

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

Answer 3

Utilisez le travail des hachages. Notez qu'il y a quelques contrôles qui pourraient être faits pour retourner immédiatement un faux, mais je montre seulement la viande du processus. Ici, il est en format d'extension pratique:

Mise à jour à poignée Référence

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

} 

Answer 4

Cette version utilise une file d'attente pour stocker les séquences possibles. Il ne passe qu'une fois à haystack une fois mis à part le Take() initial, et il arrête d'itérer une fois qu'il trouve une correspondance. Cependant, il mute des variables dans une instruction 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; 
         }); 
}