Encontrar una subsecuencia en la secuencia más larga

Question

Necesito encontrar una secuencia en otra secuencia grande, por ejemplo, {1,3,2,3} está presente en {1,3,2,3,4,3} y {5,1,3,2,3}. ¿Hay alguna forma de hacerlo rápidamente con IEnumerable o con algo más?

Answer 1

Puede probar algo como esto para comenzar. Una vez que haya convertido esta lista en una cadena, se puede encontrar la secuencia utilizando la subcadena:

if (String.Join(",", numericList.ConvertAll<string>(x => x.ToString()).ToArray()) 
{ 
    //get sequence 
} 

Answer 2

Este método se encuentra una subsecuencia dentro de una secuencia original, de cualquier tipo que pueda ser comparado a través de Equals():

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target) 
{ 
    bool foundOneMatch = false; 
    using (IEnumerator<T> parentEnum = parent.GetEnumerator()) 
    { 
     using (IEnumerator<T> targetEnum = target.GetEnumerator()) 
     { 
      // Get the first target instance; empty sequences are trivially contained 
      if (!targetEnum.MoveNext()) 
       return true; 

      while (parentEnum.MoveNext()) 
      { 
       if (targetEnum.Current.Equals(parentEnum.Current)) 
       { 
        // Match, so move the target enum forward 
        foundOneMatch = true; 
        if (!targetEnum.MoveNext()) 
        { 
         // We went through the entire target, so we have a match 
         return true; 
        } 
       } 
       else if (foundOneMatch) 
       { 
        return false; 
       } 
      } 

      return false; 
     } 
    } 
} 

se puede utilizar la siguiente manera:

bool match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 2}); // match == true 
match = new[] {1, 2, 3}.ContainsSubsequence(new[] {1, 3}); // match == false 

Nota que asume la secuencia diana no tiene null elementos.

actualización: Gracias por la upvotes, todo el mundo, pero en realidad hay un fallo en el código anterior! Si se encuentra una coincidencia parcial, pero luego no se convierte en una coincidencia completa, el proceso es finalizó, en lugar de restablecer (que obviamente está incorrecto cuando se aplica a algo como {1, 2, 1, 2, 3}.ContainsSubsequence({1, 2, 3})).

El código anterior funciona muy bien para la definición más común de subsecuencia (es decir, contigüidad no es necesaria) pero para manejar el restablecimiento (que la mayoría IEnumerators no admite) la secuencia objetivo debe enumerarse por adelantado. Esto nos lleva al siguiente código:

public static bool ContainsSubequence<T>(this IEnumerable<T> parent, IEnumerable<T> target) 
{ 
    bool foundOneMatch = false; 
    var enumeratedTarget = target.ToList(); 
    int enumPos = 0; 

    using (IEnumerator<T> parentEnum = parent.GetEnumerator()) 
    { 
     while (parentEnum.MoveNext()) 
     { 
      if (enumeratedTarget[enumPos].Equals(parentEnum.Current)) 
      { 
       // Match, so move the target enum forward 
       foundOneMatch = true; 
       if (enumPos == enumeratedTarget.Count - 1) 
       { 
        // We went through the entire target, so we have a match 
        return true; 
       } 

       enumPos++; 
      } 
      else if (foundOneMatch) 
      { 
       foundOneMatch = false; 
       enumPos = 0; 

       if (enumeratedTarget[enumPos].Equals(parentEnum.Current)) 
       { 
        foundOneMatch = true; 
        enumPos++; 
       } 
      } 
     } 

     return false; 
    } 
} 

Este código no tiene virus, pero no va a funcionar bien para las grandes secuencias (o infinito).

Answer 3

similares a @ dlev, pero éste también se encarga de {1,1,1,2}.ContainsSubsequence({1,1,2})

public static bool ContainsSubsequence<T>(this IEnumerable<T> parent, IEnumerable<T> target) 
{ 
    var pattern = target.ToArray(); 
    var source = new LinkedList<T>(); 
    foreach (var element in parent) 
    { 
     source.AddLast(element); 
     if(source.Count == pattern.Length) 
     { 
      if(source.SequenceEqual(pattern)) 
       return true; 
      source.RemoveFirst(); 
     } 
    } 
    return false; 
} 

Answer 4

Esto funciona para mí

var a1 = new List<int> { 1, 2, 3, 4, 5 }; 
var a2 = new List<int> { 2, 3, 4 }; 

int index = -1; 
bool res = a2.All(
    x => index != -1 ? (++index == a1.IndexOf(x)) : ((index = a1.IndexOf(x)) != -1) 
); 

Answer 5

Esta función comprueba si la lista parent contiene Lista target el uso de algunos de LINQ:

public static bool ContainsSequence<T>(this List<T> parent, List<T> target) 
    { 
     for (int fromElement = parent.IndexOf(target.First()); 
      (fromElement != -1) && (fromElement <= parent.Count - target.Count); 
      fromElement = parent.FindIndex(fromElement + 1, p => p.Equals(target.First()))) 
     { 
      var comparedSequence = parent.Skip(fromElement).Take(target.Count); 
      if (comparedSequence.SequenceEqual(target)) return true; 
     } 
     return false; 
    }  

Answer 6

Si está manejando serializables simples tipos, se puede hacer eso con bastante facilidad si convierte las matrices de cadena:

public static bool ContainsList<T>(this List<T> containingList, List<T> containedList) 
{ 
    string strContaining = "," + string.Join(",", containingList) + ","; 
    string strContained = "," + string.Join(",", containedList) + ","; 
    return strContaining.Contains(strContained); 
} 

Tenga en cuenta que es un método de extensión, por lo que serán capaces de llamar así:

if (bigList.ContainsList(smallList)) 
{ 
    ... 
}