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.
ds.algorithms
sorting
permutations
edit-distance
emchristiansen
fuente
fuente
Respuestas:
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.
fuente