Número mínimo de transposições para classificar uma lista

15

Ao tentar criar meu próprio algoritmo de classificação, estou procurando o benchmark ideal com o qual posso compará-lo. Para uma ordem não classificada dos elementos A e uma ordem classificada B , qual é uma maneira eficiente de calcular o número ideal de transposições para ir de A a B ?

Uma transposição é definida como alternar a posição de 2 elementos na lista, portanto, por exemplo

1 2 4 3

tem uma transposição (transposição 4 e 3) para torná-lo

1 2 3 4

Algo como

1 7 2 5 9 6

requer 4 transposições (7, 2), (7, 6), (6,5), (9, 7)

Atualização (7/9/11): a pergunta foi alterada para usar "transposição" em vez de "swaps" para se referir a trocas não adjacentes.

sova
fonte
e se você puder trocar de vizinhos? como posso descobrir o número mínimo de swaps?

Respostas:

23

Se você está lidando apenas com permutações de elementos, precisará de exatamente n - c ( π ) swaps, onde c ( π ) é o número de ciclos na decomposição do ciclo separado de π . Uma vez que esta distância é bi-invariante, transformando π em σ (ou A em B , ou vice-versa) requer n - c ( σ - 1pi ) tais movimentos.nn-c(π)c(π)ππσUMABn-c(σ-1 1π)

Anthony Labarre
fonte
Apesar de votar a muito tempo atrás, apenas clicou hoje. Como um cubo de Rubik, certo: D?
S05
11

A distância de troca também pode ser incorporada isometricamente no espaço euclidiano. Para cada string s, construa uma matriz que M i j = 1 se i ocorrer antes de j e for zero, caso contrário. Então a distância de Frobenius - M ( s ) - M ( s ' ) - 2 é a distância de troca d ( s , s ' ) . (dos slides de Graham Cormode ). Não é tão elegante quanto a resposta de Anthony, mas bastante fácil de calcular.M(s)MEuj=1 1Euj__M(s)-M(s)__2d(s,s)

Atualização: veja os comentários de Oleksandr

Suresh Venkat
fonte
Parece-me que, na apresentação de Graham, eles significam norma espectral ( ) e não norma de Frobenius ( " A ")__UMA__2 ). __UMA__F
Oleksandr Bondarenko
embora se tudo o que você quer fazer é contar as diferenças, o quadrado da norma frobenius deve funcionar corretamente?
Suresh Venkat
que é, naturalmente, a distância Hamming para 0-1 matrizes
Suresh Venkat
Você está certo sobre a igualdade entre o quadrado da norma Frobenius e a distância de Hamming. Gostaria de acrescentar que a distância de Hamming dividida por é igual à distância de troca. Mas a questão era sobre a distância de transposição ("Uma troca é definida como alternar a posição de 2 elementos na lista") e não sobre a distância de troca. No que diz respeito à norma espectral, é o quadrado igual a trocar distância.2
Oleksandr Bondarenko
Oleksandr: Então, suponho que você interprete "troca" como "trocando dois elementos adjacentes"?
Anthony Labarre