La mejor manera de reducir secuencias en una matriz de cadenas

Question

Por favor, ahora que he vuelto a escribir la pregunta, y antes de que sufra de fast-gun answers o cierre prematuro por eager editors déjeme señalar que este no es un duplicado de this question . Sé cómo eliminar duplicados de una matriz.

Esta pregunta trata de eliminar las secuencias de una matriz, no duplicados en el sentido estricto.

Considere esta secuencia de elementos en una matriz;

[0] a 
[1] a 
[2] b 
[3] c 
[4] c 
[5] a 
[6] c 
[7] d 
[8] c 
[9] d 

En este ejemplo quiero obtener la siguiente ...

[0] a 
[1] b 
[2] c 
[3] a 
[4] c 
[5] d 

Aviso que duplican elementos se retienen pero que las secuencias de un mismo elemento se han reducido a una única instancia de ese elemento.

Además, observe que cuando dos líneas se repiten, deben reducirse a un conjunto (de dos líneas).

[0] c 
[1] d 
[2] c 
[3] d 

... se reduce a ...

[0] c 
[1] d 

estoy de codificación en C#, pero algoritmos en cualquier idioma apreciado.

Answer 1

Aquí está la aplicación de C# que resuelve este problema.

toma
aabccacdcd

salidas
abcacd

Probablemente se ve muy desordenado, me llevó un poco para conseguir mi cabeza alrededor de la broca longitud del patrón dinámico.

class Program 
{ 
    private static List<string> values; 
    private const int MAX_PATTERN_LENGTH = 4; 

    static void Main(string[] args) 
    { 
     values = new List<string>(); 
     values.AddRange(new string[] { "a", "b", "c", "c", "a", "c", "d", "c", "d" }); 


     for (int i = MAX_PATTERN_LENGTH; i > 0; i--) 
     { 
      RemoveDuplicatesOfLength(i); 
     } 

     foreach (string s in values) 
     { 
      Console.WriteLine(s); 
     } 
    } 

    private static void RemoveDuplicatesOfLength(int dupeLength) 
    { 
     for (int i = 0; i < values.Count; i++) 
     { 
      if (i + dupeLength > values.Count) 
       break; 

      if (i + dupeLength + dupeLength > values.Count) 
       break; 

      var patternA = values.GetRange(i, dupeLength); 
      var patternB = values.GetRange(i + dupeLength, dupeLength); 

      bool isPattern = ComparePatterns(patternA, patternB); 

      if (isPattern) 
      { 
       values.RemoveRange(i, dupeLength); 
      } 
     } 
    } 

    private static bool ComparePatterns(List<string> pattern, List<string> candidate) 
    { 
     for (int i = 0; i < pattern.Count; i++) 
     { 
      if (pattern[i] != candidate[i]) 
       return false; 
     } 

     return true; 
    } 
} 

fija los valores iniciales para que coincida con los valores preguntas

Answer 2

Yo los volcaría a todos en su implementación de Set favorita.

EDIT: Ahora que entiendo la pregunta, su solución original parece la mejor manera de hacerlo. Simplemente recorra la matriz una vez, manteniendo una serie de indicadores para marcar qué elementos conservar, más un contador para realizar un seguimiento del tamaño de la nueva matriz. Luego recorra nuevamente para copiar todos los guardianes a una nueva matriz.

Answer 3

Estoy de acuerdo en que si solo puedes volcar las cuerdas en un conjunto, entonces esa podría ser la solución más fácil.

Si no tiene acceso a una implementación de conjunto por alguna razón, simplemente ordenaría las cadenas alfabéticamente y luego pasaría una vez y eliminaría los duplicados. La forma de ordenarlos y eliminar los duplicados de la lista dependerá del idioma y el entorno en el que ejecute el código.

EDIT: Oh, ick ... Veo, en base a su aclaración, que usted espera que los patrones puedan ocurrir incluso en líneas separadas. Mi enfoque no resolverá tu problema. Lo siento. Aquí hay una pregunta para ti. Si tuviera el siguiente archivo

un

un

b

c

c

un

un

b

c

c

¿Es de esperar que para simplificar a

un

b

c

Answer 4

EDIT: hecho algunos cambios y nuevas sugerencias

¿Qué pasa con una ventana deslizante ...

REMOVE LENGTH 2: (no other length has other matches) 
//the lower case letters are the matches 
ABCBAbabaBBCbcbcbVbvBCbcbcAB 
__ABCBABABABBCBCBCBVBVBCBCBCAB 

REMOVE LENGTH 1 (duplicate characters): 
//* denote that a string was removed to prevent continual contraction 
//of the string, unless this is what you want. 
ABCBA*BbC*V*BC*AB 
_ABCBA*BBC*V*BC*AB 

RESULT: 
ABCBA*B*C*V*BC*AB == ABCBABCVBCAB 

Esto es, por supuesto, a partir de la longitud = 2, aumentarla a L/2 y recorrer hacia abajo.

También estoy pensando en otras dos enfoques:

1. dígrafo - Establecer un dígrafo con estado con los datos e iterar sobre ella con la cadena, si se encuentra un ciclo tendrá una duplicación . No estoy seguro de lo fácil que es verificar los ciclos ... posiblemente alguna programación dinámica, por lo que podría ser equivalente al método 2 a continuación. Voy a tener que pensar en esto también por más tiempo.
2. matriz de distancia - utilizando una matriz de distancia levenstein es posible que pueda detectar la duplicación del movimiento diagonal (fuera de la diagonal) con un costo 0. Esto podría indicar la duplicación de datos. Tendré que pensar en esto más.