Encontrar eficientemente el número mínimo de transposiciones necesarias para ordenar una lista

8

Me gustaría un método eficiente para calcular la cantidad mínima de transposiciones necesarias para ordenar una lista. No necesito saber cuáles son las transposiciones en realidad.

Por ejemplo, la lista [1, 1, 2, 0] requiere 2 transposiciones:

[1, 1, 2, 0] // Start
[1, 1, 0, 2] // Swap index 2 and 3
[0, 1, 1, 2] // Swap index 0 and 2

La lista [0, 1, 0, 0] requiere 1 transposición:

[0, 1, 0, 0] // Start
[0, 0, 0, 1] // Swap index 1 and 3

La lista [2, 2, 2, 2] requiere 0 transposiciones porque ya está ordenada.

Alguna metainformación: 1) La lista puede tener elementos repetidos, por lo que simplemente no usará la distancia de Cayley entre la clasificación y la permutación de identidad . 2) Esta pregunta de desbordamiento matemático está relacionada.

emchristiansen
fuente
1
Creo que las respuestas publicadas aquí deberían fusionarse con la pregunta 4096.
Tsuyoshi Ito
1
@derekhh, esto no es un duplicado (o al menos la interpretación de la publicación es diferente en la otra pregunta). Me vinculé a la pregunta 4096 en la publicación original.
emchristiansen
3
La pregunta 4096 no establece que los elementos dados son distintos. Desafortunadamente, todas las respuestas publicadas allí asumieron esto en silencio, y este descuido puede corregirse fusionando las respuestas aquí y allá.
Tsuyoshi Ito
1
@emchristiansen Oops, lo siento, no me he dado cuenta de que ...
derekhh

Respuestas:

7

Desafortunadamente, el problema es NP-hard en general, según Amir, Hartman, Kapah, Levy y Porat (ver http://epubs.siam.org/doi/abs/10.1137/080712969 ), incluso si cada símbolo aparece como máximo tres veces. No encontré una mención de un algoritmo de aproximación de factor constante, o de algo razonablemente rápido para abordar el problema. ¿Hay alguna restricción adicional que pueda pensar en su caso?

EDITAR: los autores también dan un algoritmo de aproximación de 3/2, pero no sé si es lo suficientemente bueno para sus propósitos.

Anthony Labarre
fuente
Gracias por la referencia Estoy tratando con valores de píxeles, así que listas de enteros en [0, 255]. Una longitud de lista común es de 256 elementos.
emchristiansen
¿Puede probar que cuando tiene una solución (secuencia mínima de clasificación de transposición), siempre intercambia un número grande a la izquierda con un número más pequeño a la derecha?
Ivan Kuckir