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.
Respostas:
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 ( σ - 1 ∘ pi ) tais movimentos.n n - c ( π) c ( π) π π σ UMA B n - c ( σ- 1∘ π)
fonte
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 ) Meu j= 1 Eu j ∥ M( s ) - M( s′) ∥2 d( s , s′)
Atualização: veja os comentários de Oleksandr
fonte