Cuerda distancia, transposiciones única

Question

duplicados posible:
Counting the swaps required to convert one permutation into another

Busco un algoritmo que contaría algún tipo de distancia de cadena en la única operación permitida es de transposición de dos adyacentes caracteres. Por ejemplo:
cadena1: "madre"
string2: "moterh"
distancia: 2 (primero de intercambio "h" con "e" y obtener "Motehr" y luego "h" con "r" que resulta en "moterh ")
Sé que la distancia Damerau-Levenshtein es bastante similar a ese problema, sin embargo, requiere mucha memoria (me gustaría que funcione bastante rápido en palabras de hasta 1 000 000 caracteres). Ya he escrito esto:

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;` 

Las cadenas se representan como char [n] donde n es su longitud. Estoy bastante seguro de que hay una manera de hacerlo más rápido y estaría muy agradecido si alguien me diga cómo hacerlo o escribir algún código fuente (lo mejor sería Java/Python/C++ pero cualquier cosa sería genial).

P.S. Disculpe cualquier error de idioma, no soy inglés y aún no domino ese idioma.

Answer 1

Básicamente está pidiendo el algoritmo edit distance, pero solo permite la operación de transposición (a.k.a. intercambio, twiddling). En el libro "Introducción a los algoritmos" encontrará pistas para implementar la operación twiddle, es uno de los problemas al final del capítulo sobre programación dinámica. Además, en el libro "The Algorithm Design Manual", en el capítulo sobre programación dinámica, hay una implementación completa del algoritmo de distancia de edición en C - sin la operación de transposición (una vez más, es uno de los ejercicios propuestos al final del capítulo)

En el enlace anterior, encontrará que la forma típica de implementar el algoritmo de distancia de edición es mediante el uso de programación dinámica, que tiene un costo de O (mn) de tiempo y O (mn) de espacio. Por lo que yo sé, no hay forma de hacerlo más rápido (por ejemplo, en menos de O (mn) tiempo), pero seguramente puede hacerlo en menos espacio: siendo inteligente, puede reducir el espacio a O (m), dado que solo la fila actual y las dos filas anteriores de la tabla son necesarias para calcular el costo de una operación de transposición.

Es decir, suponiendo que solo necesite la edición distancia. Si necesita las operaciones de edición reales, está atascado usando el espacio O (mn) para reconstruir la solución si usa programación dinámica. Sin embargo, puede reducir el espacio a O (min {m, n}) y reconstruir las operaciones de edición reales, utilizando Hirschberg's algorithm.