Come verificare se l'elenco contiene un altro elenco nello stesso ordine

Question

Esiste un modo semplice in C# per controllare se l'elenco è costituito da un altro elenco ?. Ecco esempio, ho:

var list1 = new List<int>() {1, 2, 3, 4, 5, 6,}; e secondo var list2 = new List<int>() {5, 6};

questa lista è una parte del primo elenco e quindi dovrebbe restituire true.

var list1 = new List<int>() {1, 2, 3, 4, 5, 6,}; var list3 = new List<int>() {1, 3}; deve restituire falso.

Non si tratta di controllare se tutti gli elementi del primo elenco esistono nel secondo elenco ma anche sull'ordine. Deve avere lo stesso ordine.

Answer 1

questo funziona per me:

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

Questo codice utilizza Enumerable.Range a correre attraverso ogni possibile punto di partenza all'interno sequence che potrebbe essere la stessa di subsequence, e controlla se il segmento della sequence le stesse dimensioni di subsequence a questa posizione è in realtà uguale a subsequence.

Quindi per questo codice:

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

ottengo:

True 
False 

Answer 2

Grazie @GeorgeVovos & @Enigmativity per sottolineare i problemi in prima soluzione.

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

Esempio

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