Algoritmos: interesante algoritmo de diferencia

Question

Esto surgió en una situación del mundo real, y pensé que podría compartirlo, ya que podría conducir a algunas soluciones interesantes. Esencialmente, el algoritmo necesita diferir dos listas, pero déjame darte una definición más rigurosa del problema.

Formulación Matemática

Suponga que tiene dos listas, L y R cada uno de los cuales contienen elementos de algún alfabeto subyacente S. Por otra parte, estas listas tienen la propiedad de que los elementos comunes que tienen que aparecen en orden: es decir, si L[i] = R[i*] y L[j] = R[j*] y i < j continuación i * * j <. Las listas no necesitan tener ningún elemento común, y una o ambas pueden estar vacías. [Aclaración: puede suponer que no hay repeticiones de elementos.]

El problema es producir una especie de "diff" de las listas, que puede ser vista como nueva lista de pares ordenados (x,y) donde x es de L y y es de R, con las siguientes propiedades:

1. Si aparece x en ambas listas, (x,x) aparece en el resultado.
2. Si aparece x en L, pero no en R, aparece (x,NULL) en el resultado.
3. Si aparece y en R, pero no en L, aparece (NULL,y) en el resultado.

y finalmente

• La lista de resultados tiene "el mismo" ordenamiento como cada una de las listas de entrada: comparte, en términos generales, la misma propiedad de ordenación que el anterior con cada una de las listas de forma individual (ver ejemplo).

Ejemplos

L = (d) 
R = (a,b,c) 
Result = ((NULL,d), (a,NULL), (b,NULL), (c,NULL)) 

L = (a,b,c,d,e) 
R = (b,q,c,d,g,e) 
Result = ((a,NULL), (b,b), (NULL,q), (c,c), (d,d), (NULL,g), (e,e)) 

cualquier persona tiene buenos algoritmos para resolver esto? ¿Cuál es la complejidad?

Answer 1

Las listas ordenadas diferidas se pueden realizar en tiempo lineal al atravesar ambas listas y hacer comparaciones sobre la marcha. Trataré de publicar algún código de psuedo Java en una actualización.

Como no conocemos el algoritmo de ordenamiento y no podemos determinar ningún pedido basado en operadores menores o mayores, debemos considerar las listas desordenadas. Además, teniendo en cuenta cómo se van a formatear los resultados, debe analizar ambas listas (al menos hasta que encuentre una coincidencia y luego puede marcar y volver a comenzar desde allí). Todavía será el rendimiento O (n^2), o más específicamente O (nm).

Answer 2

Este es un problema bastante simple ya que ya tiene una lista ordenada.

//this is very rough pseudocode 
stack aList; 
stack bList; 
List resultList; 
char aVal; 
char bVal; 

while(aList.Count > 0 || bList.Count > 0) 
{ 
    aVal = aList.Peek; //grab the top item in A 
    bVal = bList.Peek; //grab the top item in B 

    if(aVal < bVal || bVal == null) 
    { 
    resultList.Add(new Tuple(aList.Pop(), null))); 
    } 
    if(bVal < aVal || aVal == null) 
    { 
    resultList.Add(new Tuple(null, bList.Pop())); 
    } 
    else //equal 
    { 
    resultList.Add(new Tuple(aList.Pop(), bList.Pop())); 
    } 
} 

Nota ... este código NO compilará. Simplemente se entiende como una guía.

EDITAR Basado en el OP comenta

Si el algoritmo de ordenación no se expone, a continuación, las listas deben ser considerados desordenada. Si las listas están desordenadas, entonces el algoritmo tiene una complejidad temporal de O (n^2), específicamente O (nm) donde n y m son el número de elementos en cada lista.

EDITAR algoritmo para resolver este

L (a, b, c, d, e) R (b, q, c, d, g, e)

//pseudo code... will not compile 
//Note, this modifies aList and bList, so make copies. 
List aList; 
List bList; 
List resultList; 
var aVal; 
var bVal; 

while(aList.Count > 0) 
{ 
    aVal = aList.Pop(); 
    for(int bIndex = 0; bIndex < bList.Count; bIndex++) 
    { 
     bVal = bList.Peek(); 
     if(aVal.RelevantlyEquivalentTo(bVal) 
     { 
     //The bList items that come BEFORE the match, are definetly not in aList 
     for(int tempIndex = 0; tempIndex < bIndex; tempIndex++) 
     { 
      resultList.Add(new Tuple(null, bList.Pop())); 
     } 
     //This 'popped' item is the same as bVal right now 
     resultList.Add(new Tuple(aVal, bList.Pop())); 

     //Set aVal to null so it doesn't get added to resultList again 
     aVal = null; 

     //Break because it's guaranteed not to be in the rest of the list 
     break; 
     } 
    } 
    //No Matches 
    if(aVal != null) 
    { 
     resultList.Add(new Tuple(aVal, null)); 
    } 
} 
//aList is now empty, and all the items left in bList need to be added to result set 
while(bList.Count > 0) 
{ 
    resultList.Add(new Tuple(null, bList.Pop())); 
} 

El conjunto de resultados será

L (a, b, c, d, e) R (b, q, c, d, g, e)

resultado ((a, null), (b , b), (nulo, q), (c , c), (d, d), (nulo, g), (e, e))

Answer 3

Ninguna respuesta real tangible, solo vaga intuición. Como no conoce el algoritmo de ordenamiento, solo indica que los datos están ordenados en cada lista, suena vagamente a los algoritmos utilizados para "diferir" archivos (por ejemplo, en Beyond Compare) y combina secuencias de líneas. O también vagamente similar a los algoritmos de expresión regular.

También puede haber múltiples soluciones. (no importa, no si no hay elementos repetidos que están estrictamente ordenados. Estaba pensando demasiado en la línea de comparaciones de archivos)

Answer 4

No creo que tenga suficiente información. Todo lo que ha afirmado es que los elementos que coinciden coinciden en el mismo orden, pero encontrar el primer par coincidente es una operación O (nm) a menos que tenga algún otro orden que pueda determinar.

Answer 5

El peor caso, tal como se define y usa solo la igualdad, debe ser O (n * m). Considere las siguientes dos listas:

A [] = {a, b, c, d, e, f, g}

B [] = {h, ​​i, j, k, l, m, n}

Suponga que existe exactamente una coincidencia entre esas dos listas "ordenadas". Tomará comparaciones O (n * m) ya que no existe una comparación que elimine la necesidad de otras comparaciones más adelante.

Por lo tanto, cualquier algoritmo que se te ocurra será O (n * m) o algo peor.

Answer 6

Hay una forma de hacerlo en O (n), si está dispuesto a hacer una copia de una de las listas en una estructura de datos diferente. Este es un intercambio clásico de tiempo/espacio.

Cree un mapa hash de la lista R, con la clave siendo el elemento y el valor siendo el índice original en la matriz; en C++, puede usar unordered_map desde tr1 o boost.

Mantenga un índice en la parte no procesada de la lista R, inicializada en el primer elemento.

Para cada elemento en la lista L, compruebe el mapa hash para ver si hay una coincidencia en la lista R. Si no encuentra ninguno, indique (valor L, NULO). Si hay una coincidencia, obtenga el índice correspondiente del mapa hash.Para cada elemento no procesado en la lista R hasta el índice coincidente, salida (valor NULL, R). Para el partido, salida (valor, valor).

Cuando haya llegado al final de la lista L, revise los elementos restantes de la lista R y los resultados (valor NULL, R).

Edit: Aquí está la solución en Python. Para aquellos que dicen que esta solución depende de la existencia de una buena función hashing, por supuesto que sí. El póster original puede agregar restricciones adicionales a la pregunta si esto es un problema, pero tomaré una postura optimista hasta entonces.

def FindMatches(listL, listR): 
    result=[] 
    lookupR={} 
    for i in range(0, len(listR)): 
     lookupR[listR[i]] = i 
    unprocessedR = 0 
    for left in listL: 
     if left in lookupR: 
      for right in listR[unprocessedR:lookupR[left]]: 
       result.append((None,right)) 
      result.append((left,left)) 
      unprocessedR = lookupR[left] + 1 
     else: 
      result.append((left,None)) 
    for right in listR[unprocessedR:]: 
     result.append((None,right)) 
    return result 

>>> FindMatches(('d'),('a','b','c')) 
[('d', None), (None, 'a'), (None, 'b'), (None, 'c')] 
>>> FindMatches(('a','b','c','d','e'),('b','q','c','d','g','e')) 
[('a', None), ('b', 'b'), (None, 'q'), ('c', 'c'), ('d', 'd'), (None, 'g'), ('e','e')] 

Answer 7

Ésta es exactamente igual que la alineación de secuencias, se puede utilizar el algoritmo Needleman-Wunsch para resolverlo. El enlace incluye el código en Python. Solo asegúrese de establecer la puntuación de manera que la falta de coincidencia sea negativa y la coincidencia sea positiva y la alineación con un espacio en blanco sea 0 al maximizar. El algoritmo se ejecuta en O (n * m) tiempo y espacio, pero la complejidad del espacio de este se puede mejorar.

de puntuación función

int score(char x, char y){ 
    if ((x == ' ') || (y == ' ')){ 
     return 0; 
    } 
    else if (x != y){ 
     return -1; 
    } 
    else if (x == y){ 
     return 1; 
    } 
    else{ 
     puts("Error!"); 
     exit(2); 
    } 
} 

Código

#include <stdio.h> 
#include <stdbool.h> 

int max(int a, int b, int c){ 
    bool ab, ac, bc; 
    ab = (a > b); 
    ac = (a > c); 
    bc = (b > c); 
    if (ab && ac){ 
     return a; 
    } 
    if (!ab && bc){ 
     return b; 
    } 
    if (!ac && !bc){ 
     return c; 
    } 
} 

int score(char x, char y){ 
    if ((x == ' ') || (y == ' ')){ 
     return 0; 
    } 
    else if (x != y){ 
     return -1; 
    } 
    else if (x == y){ 
     return 1; 
    } 
    else{ 
     puts("Error!"); 
     exit(2); 
    } 
} 


void print_table(int **table, char str1[], char str2[]){ 
    unsigned int i, j, len1, len2; 
    len1 = strlen(str1) + 1; 
    len2 = strlen(str2) + 1; 
    for (j = 0; j < len2; j++){ 
     if (j != 0){ 
      printf("%3c", str2[j - 1]); 
     } 
     else{ 
      printf("%3c%3c", ' ', ' '); 
     } 
    } 
    putchar('\n'); 
    for (i = 0; i < len1; i++){ 
     if (i != 0){ 
      printf("%3c", str1[i - 1]); 
     } 
     else{ 
      printf("%3c", ' '); 
     } 
     for (j = 0; j < len2; j++){ 
      printf("%3d", table[i][j]); 
     } 
     putchar('\n'); 
    } 
} 

int **optimal_global_alignment_table(char str1[], char str2[]){ 
    unsigned int len1, len2, i, j; 
    int **table; 
    len1 = strlen(str1) + 1; 
    len2 = strlen(str2) + 1; 
    table = malloc(sizeof(int*) * len1); 
    for (i = 0; i < len1; i++){ 
     table[i] = calloc(len2, sizeof(int)); 
    } 
    for (i = 0; i < len1; i++){ 
     table[i][0] += i * score(str1[i], ' '); 
    } 
    for (j = 0; j < len1; j++){ 
     table[0][j] += j * score(str1[j], ' '); 
    } 
    for (i = 1; i < len1; i++){ 
     for (j = 1; j < len2; j++){ 
      table[i][j] = max(
       table[i - 1][j - 1] + score(str1[i - 1], str2[j - 1]), 
       table[i - 1][j] + score(str1[i - 1], ' '), 
       table[i][j - 1] + score(' ', str2[j - 1]) 
      ); 
     } 
    } 
    return table; 
} 

void prefix_char(char ch, char str[]){ 
    int i; 
    for (i = strlen(str); i >= 0; i--){ 
     str[i+1] = str[i]; 
    } 
    str[0] = ch; 
} 

void optimal_global_alignment(int **table, char str1[], char str2[]){ 
    unsigned int i, j; 
    char *align1, *align2; 
    i = strlen(str1); 
    j = strlen(str2); 
    align1 = malloc(sizeof(char) * (i * j)); 
    align2 = malloc(sizeof(char) * (i * j)); 
    align1[0] = align2[0] = '\0'; 
    while((i > 0) && (j > 0)){ 
     if (table[i][j] == (table[i - 1][j - 1] + score(str1[i - 1], str2[j - 1]))){ 
      prefix_char(str1[i - 1], align1); 
      prefix_char(str2[j - 1], align2); 
      i--; 
      j--; 
     } 
     else if (table[i][j] == (table[i - 1][j] + score(str1[i-1], ' '))){ 
      prefix_char(str1[i - 1], align1); 
      prefix_char('_', align2); 
      i--; 
     } 
     else if (table[i][j] == (table[i][j - 1] + score(' ', str2[j - 1]))){ 
      prefix_char('_', align1); 
      prefix_char(str2[j - 1], align2); 
      j--; 
     } 
    } 
    while (i > 0){ 
     prefix_char(str1[i - 1], align1); 
     prefix_char('_', align2); 
     i--; 
    } 
    while(j > 0){ 
     prefix_char('_', align1); 
     prefix_char(str2[j - 1], align2); 
     j--; 
    } 
    puts(align1); 
    puts(align2); 
} 

int main(int argc, char * argv[]){ 
    int **table; 
    if (argc == 3){ 
     table = optimal_global_alignment_table(argv[1], argv[2]); 
     print_table(table, argv[1], argv[2]); 
     optimal_global_alignment(table, argv[1], argv[2]); 
    } 
    else{ 
     puts("Reqires to string arguments!"); 
    } 
    return 0; 
} 

Muestra IO

$ cc dynamic_programming.c && ./a.out aab bba 
__aab 
bb_a_ 
$ cc dynamic_programming.c && ./a.out d abc 
___d 
abc_ 
$ cc dynamic_programming.c && ./a.out abcde bqcdge 
ab_cd_e 
_bqcdge 

Answer 8

SELECT l.el distinta ement, r.element
DE LeftList l
OUTER JOIN r RightList
EN l.element = r.element
ORDER BY l.id, r.id

asume la ID de cada elemento es su ordenamiento . Y por supuesto, que sus listas están contenidas en una base de datos relacional :)