Encontrar com eficiência o número mínimo de transposições necessárias para classificar uma lista

8

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.

emchristiansen
fonte
1
Acho que a resposta (s) postado aqui deveriam ser fundidas à pergunta 4096.
Tsuyoshi Ito
1
@derekhh, isso não é uma cópia (ou pelo menos a interpretação do post é diferente na outra pergunta). Eu liguei para a pergunta 4096 no post original.
emchristiansen
3
A pergunta 4096 não afirma que os elementos fornecidos são distintos. Infelizmente, todas as respostas postadas lá assumiram silenciosamente isso, e essa supervisão pode ser corrigida mesclando as respostas aqui para lá.
Tsuyoshi Ito
1
@emchristiansen Opa, desculpe, eu não tenho notado que ...
derekhh

Respostas:

7

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.

Anthony Labarre
fonte
Obrigado pela referência. Estou lidando com valores de pixel, então listas de números inteiros em [0, 255]. Um comprimento de lista comum é de 256 elementos.
Emchristiansen
Você pode provar que, quando você tem uma solução (sequência de classificação mínima de transposição), sempre troca um número grande à esquerda por um número menor à direita?
precisa saber é o seguinte