Encontrar una distancia mínima entre listas clasificadas y sin clasificar

Sea A una lista y S una lista ordenada de los mismos elementos. Supongamos que todos los elementos son diferentes. ¿Cómo encuentro un conjunto mínimo de “movimientos” ( move X before Y (or end) ) que convierte A en S?

Ejemplos:

 A = [8,1,2,3] S = [1,2,3,8] A => S requires one move: move 8 before end A = [9,1,2,3,0] S = [0,1,2,3,9] A => S requires two moves: move 9 before 0 move 0 before 1 

Prefiero javascript o python, pero cualquier idioma servirá.

Este problema es equivalente al problema de subsecuencia cada vez mayor .

Tendrás que definir un operador de comparación less . less(a, b) devolverá true si y solo si a está antes de b en la secuencia de destino. Ahora, utilizando este operador de comparación, calcule la secuencia secundaria de aumento máximo de la secuencia de origen. Tendrá que mover cada elemento que no sea parte de esta secuencia secundaria (de lo contrario, la secuencia secundaria no será la máxima) y puede moverlo exactamente una vez (moviéndolo a su posición de destino).

EDITAR: según lo solicitado por amit, aquí está mi prueba de la afirmación anterior: nos permite denotar la secuencia de destino B y la de origen A Sea n = |A| y sea k la longitud de la secuencia creciente más larga como se describe anteriormente.

  • Asummos que es posible alcanzar B desde A con menos movimientos que n - k . Esto significa que al menos n - k + 1 elementos de la A no se moverán. Sean s 1 , s 2 , … s m el conjunto de elementos que no se mueven. Por el supuesto, sabemos que m > k . Ahora como estos elementos no se han movido, su posición relativa con respecto a los demás no puede haber cambiado. Por lo tanto, las posiciones relativas de todos estos elementos en la secuencia de destino B son las mismas que en A Por lo tanto, el operador less (s i , s j ) como se definió anteriormente debería ser verdadero para cualquier i , j . Pero si esto es cierto, entonces s 1 , s 2 , … s m está aumentando la secuencia y como m > k conduce a una contradicción con la suposición de que k es la longitud de la secuencia creciente más larga.
  • Ahora, mostremos un algoritmo para llegar a B desde A moviendo todos los elementos excepto los que forman parte de la secuencia creciente más larga. Moveremos los elementos en el orden en que aparecen en B. No moveremos los elementos que forman parte de la secuencia de aumento más larga. Si el elemento actual es el primero en B, simplemente lo movemos al comienzo de la secuencia. De lo contrario, movemos el elemento actual justo después de la posición del elemento anterior en B. Tenga en cuenta que este elemento puede ser el elemento anterior que hemos movido o un elemento de la secuencia de aumento más larga. Tenga en cuenta que en cada paso cuando estamos a punto de mover el elemento con el índice i , todos los elementos con el índice 1, 2, ...i-1 ya estarán en las posiciones relativas correctas entre sí.

EDITAR: agregar algún código para que la respuesta sea más clara. No me siento un experto en javascript, así que siéntase libre de corregir o criticar mi solución.

Definamos una función de transform(a, s) que toma dos parámetros: lista a y b como se describe en la statement. Primero, crearé un mapa de positions que mapea cada elemento en a a su posición en s:

 var positions = {}; for (var i = 0; i < a.length; ++i) { positions[a[i]] = i; } 

Ahora que tengo esta matriz, puedo definir una función de ayuda menos como se describe en mi respuesta anterior. Less tomará dos valores a y b (y el mapa de ayuda que acabo de crear) y devolverá verdadero si y solo si a es anterior a b en s (la lista objective):

 function less(a, b, positions) { return positions[a] < positions[b]; } 

Ahora no describiré cómo podemos encontrar la subsecuencia máxima creciente en a operador de comparación. Puede echar un vistazo a esta pregunta para obtener una explicación detallada de cómo hacerlo. Simplemente asumiré que tengo una función definida:

 function max_increasing_subsequence(a, positions) 

Eso devuelve la subsecuencia máxima en aumento con respecto al operador de comparación less como se definió anteriormente (usando positions ) como una lista. Usaré tu segundo ejemplo para ilustrar lo que tenemos hasta ahora:

 A = [9,1,2,3,0] S = [0,1,2,3,9] 

Los valores en las posiciones serán los siguientes:

 positions = { 0 : 0, 1 : 1, 2 : 2, 3 : 3, 9 : 4} 

Y el resultado de max_increasing_subsequence(a, positions) será [1, 2, 3] . Por cierto, si puede haber elementos repetidos en a , puede ser mejor devolver índices en lugar de los elementos de max_increasing_subsequence (en este ejemplo en particular, la diferencia no será visible).

Ahora crearé otro mapa de ayuda para indicar cuáles son los elementos incluidos en la subsecuencia máxima creciente:

 var included = {}; l = max_increasing_subsequence(a, positions); for (var i = 0; i < l.length; ++i) { included[l[i]] = true; } 

Ahora puede terminar la solución con una sola iteración sobre s . Agregaré un caso especial para el último elemento para que el código sea más fácil de entender:

 if (!(s[s.length - 1] in included)) { console.log("Move" + s[s.length - 1] + " at the end"); } for (var i = s.length - 2; i >= 0; --i) { if (!(s[i] in included)) { console.log("Move" + s[i] + " before " + s[i + 1]); } } 

Tenga en cuenta que en la solución anterior asumo que cada vez que registra un nuevo comando, lo registra con respecto al ordenamiento de la matriz justo después de que se hayan ejecutado todos los comandos anteriores.

Así que en total creo que la transformación debería verse algo así:

 function transform(a, s) { var positions = {}; for (var i = 0; i < a.length; ++i) { positions[a[i]] = i; } var included = {}; l = max_increasing_subsequence(a, positions); var included = {}; for (var i = 0; i < l.length; ++i) { included[l[i]] = true; } if (!(s[s.length - 1] in included)) { console.log("Move" + s[s.length - 1] + " at the end"); } for (var i = s.length - 2; i >= 0; --i) { // note s.length - 2 - don't process last element if (!(s[i] in included)) { console.log("Move" + s[i] + " before " + s[i + 1]); } } } 

Espero que este código haga mi respuesta más clara.

Si considera sus dos listas como dos cadenas, por ejemplo, los números son valores en encoding ASCII, entonces el problema es equivalente al de encontrar las operaciones que le permiten transformar la primera cadena en la segunda. El número de operaciones, a su vez, es el Levenshtein o la distancia de edición entre las cadenas.

La distancia Levenshtein se puede encontrar usando la progtwigción dinámica , almacenando en una matriz las distancias entre todos los prefijos de ambas cadenas, y luego rastreando sus pasos para encontrar en cada fila de la matriz cuál es la operación óptima (la que ha necesitado la menos operaciones para llegar a ella).

El algoritmo de subsecuencia cada vez mayor más largo sugerido por @IvayloStrandjev está relacionado con el problema de subsecuencia común más largo, que a su vez está relacionado con la distancia de edición como una métrica alternativa que solo permite la inserción y la sustitución. Probablemente sea más eficaz en el espacio, ya que aprovecha el hecho de que una de las secuencias debe ser ordenada; Solo quería proporcionar una respuesta alternativa que me sea más fácil de entender.

Aquí hay una implementación en Python del algoritmo Levenshtein de matriz completa, como se describe en la página de Wikipedia vinculada anteriormente (originalmente encontrada en un artículo de 1974 por Wagner y Fischer ), donde también se proporciona una prueba de corrección . Aquí también almacenamos los nombres de las operaciones en una matriz del mismo tamaño que las puntuaciones de las operaciones, e imprimimos la operación óptima después de completar una fila.

 import argparse import numpy as np class Levenshtein(object): def __init__(self, string1, string2): self.string1 = string1 self.string2 = string2 self.scores_matrix = np.zeros( (len(self.string1) + 1, len(self.string2) + 1), dtype=np.int16) self.operations_matrix = np.empty_like( self.scores_matrix, dtype=(np.str_, 16)) self.total_steps = 0 def distance(self): m = len(self.string1) + 1 n = len(self.string2) + 1 for i in range(m): self.scores_matrix[i, 0] = i for j in range(n): self.scores_matrix[0, j] = j for j in range(1, n): for i in range(1, m): if self.string1[i - 1] == self.string2[j - 1]: self.scores_matrix[i, j] = self.scores_matrix[i - 1, j - 1] self.operations_matrix[i, j] = 'match' else: self.scores_matrix[i, j] = self.select_operation(i, j) if j == n - 1: # a row is complete self.determine_best_op_and_print(i) return self.scores_matrix[m - 1, n - 1] def select_operation(self, i, j): possible_ops = ['delete', 'insert', 'substitute'] ops_scores = [ self.scores_matrix[i - 1, j] + 1, # deletion self.scores_matrix[i, j - 1] + 1, # insertion self.scores_matrix[i - 1, j - 1] + 1] # substitution chosen_op = min(ops_scores) chosen_op_name = possible_ops[ops_scores.index(chosen_op)] self.operations_matrix[i, j] = chosen_op_name return chosen_op def determine_best_op_and_print(self, i): reversed_row = self.scores_matrix[i][::-1] reversed_pos_min = np.argmin(reversed_row) pos_min = len(self.scores_matrix[i]) - (reversed_pos_min + 1) best_op_name = self.operations_matrix[i, pos_min] if best_op_name != 'match': self.total_steps += 1 print best_op_name, self.string1[i - 1], self.string2[pos_min - 1] def parse_cli(): parser = argparse.ArgumentParser() parser.add_argument('--list', nargs='*', required=True) return parser.parse_args() if __name__ == '__main__': args = parse_cli() A = args.list S = sorted(A) lev = Levenshtein(A, S) dist = lev.distance() print "{} total steps were needed; edit distance is {}".format( lev.total_steps, dist) 

A continuación, se explica cómo ejecutar el código con los ejemplos que proporciona y el resultado esperado:

 $ python levenshtein.py --list 8 1 2 3 substitute 8 1 1 total steps were needed; edit distance is 2 $ python levenshtein.py --list 9 1 2 3 0 substitute 9 0 substitute 0 9 2 total steps were needed; edit distance is 2 

Esto depende en gran medida de algunos parámetros del problema que no se mencionan. En primer lugar, ¿qué movimientos son legales? ¿Intercambios de elementos vecinos solamente? ¿Alguna supresión e inserción arbitraria? Segundo, ¿solo necesita la cantidad de movimientos o necesita una lista de movimientos específicos para realizar? Esto conduce a diferentes algoritmos para esto:

  1. Solo intercambios vecinos: esto se denomina conteo de inversión, si solo le importa el número mínimo.
  2. Eliminaciones, intercambios no vecinos, etc. – La distancia de Levenshtein, mencionada anteriormente, es una distancia de edición más general. Un truco sobre esto es cómo define su conjunto de movimientos. ¿Se está moviendo un elemento 3 lugares sobre un solo movimiento o son dos movimientos (una eliminación y una inserción)?

Los recuentos de inversión son bastante simples y se pueden realizar con algunos algoritmos recursivos básicos. Puede usar una ordenación de combinación para encontrar el recuento de inversión entre dos listas utilizando una lista para hacer una versión transformada de la otra, donde los nuevos elementos son índices. Así que si tienes dos secuencias, puedes hacer:

 sequence = [seq2.index(element) for element in seq] 

Una implementación simple de fusión y ordenación directa de Python para contar las inversiones es:

 if len(sequence) <= 1: return 0, sequence else: firstHalf = sequence[:int(len(sequence)/2)] secondHalf = sequence[int(len(sequence)/2):] count1, firstHalf = mergeSortInversionCount(firstHalf) count2, secondHalf = mergeSortInversionCount(secondHalf) firstN = len(firstHalf) secondN = len(secondHalf) secondHalfEnd = secondN count3 = count1 + count2 # Count the inversions in the merge # Uses a countdown through each sublist for i in xrange(firstN-1, -1, -1): x = firstHalf[i] inversionFound = False for j in xrange(secondHalfEnd-1,-1,-1): if x > secondHalf[j]: inversionFound = True break if inversionFound: secondHalfEnd = j+1 count3 += j+1 mergeList = firstHalf + secondHalf mergeList.sort() return count3, mergeList 

Esto solo divide la lista a la mitad y cuenta las inversiones, ordenando la lista a medida que avanza. La clasificación de fusión es bastante eficiente, hablando algorítmicamente (NlogN, aunque prácticamente se puede calcular más rápidamente con algunas matrices numpy o desarrollando una pequeña adaptación al código C para el algoritmo de clasificación Python subyacente. Técnicamente, dado que este enfoque transforma cualquier El tipo de variables en números se reduce básicamente a un enfoque de ordenación de listas, por lo que puede usar otras clasificaciones de listas de elementos para hacer lo mismo, siempre que haga un seguimiento de la cuenta.

Con cualquiera de estos métodos (conteo de inversión, Levenstein, etc.), puede registrar los movimientos, claramente. Los recuentos de inversión registran los intercambios, logc observó un enfoque razonable para registrar algunos movimientos más generales para Levenstein. Personalmente, tiendo a usar cuentas de inversión para esto porque son bastante simples. Pero depende mucho de lo que quieras. Si necesita más operaciones que intercambios de vecinos de dos elementos, Levenstein es una opción clara.

Realice un Ciclo de clasificación y cuente el número de movimientos. Eso está garantizado para ser el número mínimo.