Eu gostaria de um método eficiente para calcular o número mínimo de transposições necessárias para classificar uma lista. Não preciso saber quais são realmente as transposições.
Por exemplo, a lista [1, 1, 2, 0] requer 2 transposições:
[1, 1, 2, 0] // Start
[1, 1, 0, 2] // Swap index 2 and 3
[0, 1, 1, 2] // Swap index 0 and 2
A lista [0, 1, 0, 0] requer 1 transposição:
[0, 1, 0, 0] // Start
[0, 0, 0, 1] // Swap index 1 and 3
A lista [2, 2, 2, 2] requer 0 transposições porque já está classificada.
Algumas informações meta: 1) A lista pode ter elementos repetidos; portanto, o simples uso da distância de Cayley entre o tipo e a permutação de identidade não funcionará . 2) Esta questão do estouro de matemática está relacionada.
ds.algorithms
sorting
permutations
edit-distance
emchristiansen
fonte
fonte
Respostas:
Infelizmente, o problema é difícil para os NP em geral, de acordo com Amir, Hartman, Kapah, Levy e Porat (consulte http://epubs.siam.org/doi/abs/10.1137/080712969 ), mesmo que cada símbolo apareça no máximo. três vezes.
Não encontrei menção a um algoritmo de aproximação de fator constante ou a algo razoavelmente rápido para resolver o problema. Existem restrições adicionais em que você pode pensar no seu caso?EDIT: os autores também fornecem um algoritmo de aproximação de 2/2, mas não sei se é bom o suficiente para seus propósitos.
fonte