Algoritmo: forma óptima de reorganizar una lista de una orden a otra?

Question

EDITAR: No estoy seguro de que mi pregunta original sea lo suficientemente clara. Necesito un algoritmo que calculará la secuencia mínima de movimientos para reorganizar una matriz de una orden a otra. Se sabe que ambas matrices contendrán los mismos elementos (sin duplicados) y tendrán la misma longitud. Por ejemplo:

reorder(
    ['d', 'a', 'c', 'b', 'e'], 
    ['a', 'b', 'c', 'd', 'e'] 
) 

debería devolver algo como:

[ 
    {move:'d', after:'b'}, 
    {move:'c', after:'b'} 
] 

que indica que debería mover primero el elemento de 'd' para después 'b', a continuación, pasar 'c' para después 'b' y la matriz estará en el orden deseado.

---

Antecedentes: Estoy trabajando en un proyecto (que se mueve la mayor parte de la funcionalidad en rtgui para el lado del cliente, en realidad). En este momento estoy trabajando en la clasificación. Básicamente, tengo una lista de divs que quiero ordenar en un orden arbitrario. Puedo conseguir el fin deseado de la siguiente manera:

var hashes = { 
    before: [], 
    after: [], 
}; 
var els = $('div.interesting-class').toArray(); 
var len = els.length; 

for(var i = 0; i < len; i++) hashes.before.push(els[i].id); 
els.sort(getSortComparator()); 
for(var i = 0; i < len; i++) hashes.after.push(els[i].id); 

Ahora hashes.before y hashes.after contienen la desordenada y ordenó listas de identificadores de elementos. Al reordenar la lista, la operación más cara, de lejos, está moviendo realmente los elementos DOM. Había estado haciendo esto de la siguiente manera:

var c = $('#container-id'); 
$(els).each(function() { 
    c.append(this); 
}); 

Esto funciona, pero es más lento de lo necesario, ya que, en promedio, sólo 2 o 3 elementos realmente necesita ser movido. Por lo tanto, Necesito un algoritmo que calculará la secuencia mínima de movimientos para reorganizar una matriz de una orden a otra (en este caso, operando en hashes.before y). ¿Alguien puede sugerir uno o dar alguna idea?

He probado varios algoritmos de "diff" de uso general hasta ahora, pero en realidad no me dieron lo que quería. Creo que lo que necesito es así, pero más especializado.

Answer 1

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Encuentra la más larga subsecuencia creciente (de acuerdo con el nuevo orden de clasificación). Luego mueva cada elemento que no está en esa secuencia, a su lugar relativo a los elementos que ya están en la secuencia.

En su ejemplo, 'a, b, e' y 'a, c, e' están vinculados a la subsecuencia creciente más larga. Lo mejor que puedes hacer es elegir uno de ellos, y solo mover los otros elementos.

Answer 2

Mi primer pensamiento es que debería usar Selection sort en lugar del método de clasificación incorporado, ya que hace la cantidad más baja de intercambios necesarios. De esta forma, puede mover el elemento DOM al mover la identificación en la lista.

Answer 3

Divida las claves y los índices de la matriz en una matriz separada de objetos {clave, índice}. Clasifique esa matriz (usando la mejor clasificación que pueda, por supuesto, ya sea una clasificación de fusión si las comparaciones son caras o una oferta rápida si son baratas). Ahora sabe, a partir de los índices reales en la matriz ordenada y los valores de índice almacenados en cada elemento, cómo reorganizar la matriz original.

Una vez que haya ordenado las claves, el número "óptimo" de movimientos será el O (n) de la matriz original. Si desea reorganizar la matriz original en su lugar, puede derivar los intercambios de su lista ordenada de índices de forma bastante simple.

Answer 4

Knuth Volume 3 tiene una sección sobre "redes de clasificación". No entra en un lote lote de detalles sobre cómo construir redes de comparación mínimas, pero sí cita algún trabajo (por ejemplo, por parte de Batcher y él mismo) sobre cómo construirlos. Tenga en cuenta que si bien estas son notas como "redes de comparación mínima", pocas (si las hay) de ellas han sido realmente probados como, son intentos de minimizar el número de comparadores necesarios, pero no necesariamente exitosos en términos de realmente logrando el verdadero mínimo.