String distanza, trasposizioni solo

Question

Eventuali duplicati:
Counting the swaps required to convert one permutation into another

Sto cercando un algoritmo che conterebbe una sorta di distanza stringa dove consentito solo il funzionamento è la trasposizione di due adiacenti personaggi. Per esempio:
string1: "madre"
string2: "moterh"
distanza: 2 (primo swap "h" con "e" e ottenere "motehr" e poi "h" con la "r" con conseguente "moterh ")
So che la distanza di Damerau-Levenshtein è abbastanza simile a quel problema, ma richiede molta memoria (mi piacerebbe che fosse abbastanza veloce con parole fino a 1 000 000 caratteri). Ho già scritto questo:

int amo = 0; 

for (int i = 0; i < n; i++) 
{ 
    if (fromString[i] == toString[i]) 
     continue; 
    char toWhat = toString[i]; 
    int where = -1; 
    for (int j = i; j < n; j++) 
    { 
     if (fromString[j] == toWhat) 
     { 
      where = j; 
      break; 
     } 
    } 
    while (where != i) 
    { 
     char temp = fromString[where]; 
     fromString[where] = fromString[where - 1]; 
     fromString[where - 1] = temp; 
     where--; 
     amo++; 
    } 
} 
cout << amo << endl;` 

stringhe sono rappresentate come char [n] dove n è la loro lunghezza. Sono abbastanza sicuro che c'è un modo per farlo più velocemente e sarei molto grato se qualcuno mi dirà come farlo o scrivere un codice sorgente (meglio sarebbe Java/Python/C++ ma tutto è fantastico).

P.S. Scusami eventuali errori linguistici, non sono inglese e non ho ancora imparato la lingua.

Answer 1

Fondamentalmente si sta richiedendo l'algoritmo edit distance, ma si consente solo l'operazione di trasposizione (a.k.a. swapping, twiddling). Nel libro "Introduzione agli algoritmi" troverai indizi per implementare l'operazione di twiddle, è uno dei problemi alla fine del capitolo sulla programmazione dinamica. Inoltre, nel libro "The Algorithm Design Manual", nel capitolo sulla programmazione dinamica, c'è un'implementazione completa dell'algoritmo di modifica della distanza in C - l'operazione di trasposizione (di nuovo, è uno degli esercizi proposti alla fine del capitolo).

Nel collegamento precedente, scoprirete che il modo tipico per implementare l'algoritmo di modifica della distanza è utilizzando la programmazione dinamica, che ha un costo di tempo O (mn) e O (mn). Per quanto ne so, non c'è modo di farlo più velocemente (ad esempio in meno di O (mn)), ma sicuramente puoi farlo in meno spazio - essendo intelligente, puoi ridurre lo spazio a O (m), dato che solo la riga corrente e le due righe precedenti nella tabella sono necessarie per calcolare il costo di un'operazione di trasposizione.

Supponendo che sia necessaria solo la modifica distanza. Se hai bisogno delle effettive operazioni di modifica, sei bloccato usando O (mn) per ricostruire la soluzione se utilizzando la programmazione dinamica. Tuttavia, è possibile ridurre lo spazio a O (min {m, n}) e ricostruire le operazioni di modifica effettive, utilizzando Hirschberg's algorithm.