: Algoritmo diffidente interessante

Question

Questo è venuto in una situazione del mondo reale, e ho pensato di condividerlo, in quanto potrebbe portare ad alcune soluzioni interessanti. Essenzialmente, l'algoritmo ha bisogno di diff due liste, ma lascia che ti dia una definizione più rigorosa del problema.

matematica Formulazione

Supponiamo di avere due liste, L e R ognuno dei quali contengono elementi da alcune alfabeto sottostante S. Inoltre, queste liste hanno la proprietà che gli elementi comuni che hanno appaiono in ordine: vale a dire, se L[i] = R[i*] e L[j] = R[j*], e i < j poi i * < j *. Gli elenchi non hanno bisogno di elementi comuni e uno o entrambi possono essere vuoti. [Chiarimento: non si può assumere alcuna ripetizione di elementi.]

Il problema è quello di realizzare una sorta di "diff" delle liste, che possono essere visti come nuova lista di coppie ordinate (x,y) dove x è da L e y sia residente R, con le seguenti proprietà:

1. Seappare in entrambi gli elenchi, nel risultato appare (x,x).
2. Se x appare in L, ma non in R, nel risultato appare (x,NULL).
3. Se appare in R, ma non in L, nel risultato appare (NULL,y).

e infine

• La lista dei risultati ha "lo stesso" ordinamento di ciascuna delle liste di ingresso: IT azioni, grosso modo, la stessa proprietà ordinamento come sopra, con ciascuna delle liste individualmente (vedi esempio).

Esempi

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

Qualcuno ha qualche buoni algoritmi per risolvere questo? Qual è la complessità?

Answer 1

Le liste ordinate possono essere eseguite in tempo lineare spostando entrambe le liste e facendo corrispondenze. Proverò a postare qualche codice Java di psuedo in un aggiornamento.

Dato che non conosciamo l'algoritmo di ordinamento e non possiamo determinare alcun ordine basato su operatori minori o maggiori di, dobbiamo considerare le liste non ordinate. Inoltre, dato il modo in cui i risultati devono essere formattati, devi affrontare la scansione di entrambi gli elenchi (almeno finché non trovi una corrispondenza, quindi puoi aggiungere un segnalibro e ricominciare da lì). Sarà ancora O (n^2) prestazioni, o sì più specificamente O (nm).

Answer 2

Questo è un problema piuttosto semplice poiché si dispone già di un elenco ordinato.

//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 ... questo codice non viene compilato. È solo inteso come una guida.

EDIT Sulla base del PO commenta

Se l'algoritmo ordinamento non è esposto, quindi le liste devono essere considerati non ordinata. Se gli elenchi non sono ordinati, l'algoritmo ha una complessità temporale di O (n^2), in particolare O (nm) dove n e m sono il numero di elementi in ciascuna lista.

EDIT Algoritmo per risolvere questo

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

il set di risultati sarà

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

risultato ((a, nullo), (b , b), (null, q), (c , c), (d, d), (null, g), (e, e))

Answer 3

Nessuna vera risposta tangibile, solo vaga intuizione. Poiché non si conosce l'algoritmo di ordinamento, solo che i dati sono ordinati in ogni elenco, suona vagamente come gli algoritmi utilizzati per i file "diff" (ad esempio in Beyond Compare) e corrispondono sequenze di linee insieme. O anche vagamente simile agli algoritmi regexp.

Possono esserci anche più soluzioni. (non importa, non se non ci sono elementi ripetuti che sono rigorosamente ordinati. Stavo pensando troppo lungo le linee di confronto dei file)

Answer 4

Non penso che tu abbia abbastanza informazioni. Tutto ciò che hai affermato è che gli elementi che corrispondono alla corrispondenza nello stesso ordine, ma trovare la prima coppia corrispondente è un'operazione O (nm) a meno che tu non abbia altri ordini da poter determinare.

Answer 5

Il caso peggiore, come definito e utilizzando solo l'uguaglianza, deve essere O (n * m). Considerare le seguenti due liste:

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

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

Supponiamo che esista esattamente una corrispondenza tra queste due liste "ordinate". Ci vorranno confronti O (n * m) poiché non esiste un confronto che rimuova la necessità di altri confronti in seguito.

Quindi, qualsiasi algoritmo si presenterà sarà O (n * m), o peggio.

Answer 6

C'è un modo per farlo in O (n), se si è disposti a fare una copia di uno degli elenchi in una struttura dati diversa. Questo è un classico compromesso tempo/spazio.

Creare una mappa hash dell'elenco R, con la chiave che rappresenta l'elemento e il valore che rappresenta l'indice originale nell'array; in C++, potresti usare unordered_map da tr1 o boost.

Mantiene un indice nella parte non elaborata dell'elenco R, inizializzata sul primo elemento.

Per ogni elemento nell'elenco L, controllare la mappa hash per una corrispondenza nell'elenco R. Se non ne trovi uno, output (valore L, NULL). Se c'è una corrispondenza, prendi l'indice corrispondente dalla mappa hash.Per ogni elemento non elaborato nell'elenco R fino all'indice corrispondente, output (NULL, valore R). Per la partita, uscita (valore, valore).

Una volta raggiunta la fine della lista L, passare attraverso gli elementi rimanenti dell'elenco R e dell'output (NULL, valore R).

Modifica: Ecco la soluzione in Python. Per quelli che dicono che questa soluzione dipende dall'esistenza di una buona funzione di hashing - ovviamente lo fa. Il poster originale può aggiungere ulteriori vincoli alla domanda se questo è un problema, ma assumerò una posizione ottimistica fino ad allora.

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

Questo è esattamente come l'allineamento di sequenze, è possibile utilizzare il Needleman-Wunsch algoritmo per risolverlo. Il link include il codice in Python. Assicurati solo di impostare il punteggio in modo che una corrispondenza mancata sia negativa e una corrispondenza sia positiva e un allineamento con uno spazio vuoto è 0 quando si massimizza. L'algoritmo funziona con O (n * m) di tempo e spazio, ma la complessità dello spazio può essere migliorata.

Scoring Funzione

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

Codice

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

Esempio 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

SELEZIONA l.el distinta ement, r.element
DA LeftList l
outer join r RightList
ON l.element = r.element
ORDER BY l.id, r.id

assume l'ID di ciascun elemento è suo ordinamento . E, naturalmente, che le tue liste sono contenute in un Database relazionale :)