Número mínimo de transposiciones para ordenar una lista

Al tratar de idear mi propio algoritmo de clasificación, estoy buscando el punto de referencia óptimo con el que pueda compararlo. Para una ordenación no ordenada de los elementos A y una ordenación ordenada B , ¿cuál es una manera eficiente de calcular el número óptimo de transposiciones para llegar de A a B ?

Una transposición se define como cambiar la posición de 2 elementos en la lista, por ejemplo

1 2 4 3

tiene una transposición (transposición 4 y 3) para hacerlo

1 2 3 4

Algo como

1 7 2 5 9 6

requiere 4 transposiciones (7, 2), (7, 6), (6,5), (9, 7)

Actualización (7/9/11): la pregunta cambió para usar "transposición" en lugar de "intercambios" para referirse a intercambios no adyacentes.

ds.algorithms co.combinatorics sorting sova
fuente

¿Qué pasa si solo puedes intercambiar vecinos? ¿Cómo puedo calcular el número mínimo de permutas?

Respuestas:

Si solo se trata de permutaciones de elementos, necesitará exactamente swaps, donde es el número de ciclos en la descomposición del ciclo disjunto de . Como esta distancia es bi-invariante, transformar en (o en , o viceversa) requiere tales movimientos. $n$ $n-c(\pi)$ $c(\pi)$ $\pi$ $\pi$ $\sigma$ $A$ $B$ $n-c(\sigma^{-1}\circ\pi)$

Anthony Labarre
fuente

A pesar de haber votado por esto hace mucho tiempo, solo hizo clic hoy. Como un cubo de Rubik, ¿verdad: D?

sova

La distancia de intercambio también puede integrarse isométricamente en el espacio euclidiano. Para cada cadena s, construir una matriz de donde si se produce antes de y es cero en caso contrario. Entonces la distancia de Frobenius es la distancia de intercambio . (de las diapositivas de Graham Cormode ). No es tan elegante como la respuesta de Anthony, pero es bastante fácil de calcular. $M(s)$ $M_{ij} = 1$ $i$ $j$ $\|M(s) - M(s')\|^2$ $d(s,s')$

Actualización: por favor vea los comentarios de Oleksandr

Suresh Venkat
fuente

Me parece que en la presentación de Graham quieren decir norma espectral ( ) y no norma de Frobenius ( ).

‖ A ‖_{2}

$\|A\|_2$

‖ A ‖_{F}

$\|A\|_F$

Oleksandr Bondarenko

aunque si todo lo que quieres hacer es contar las diferencias, entonces el cuadrado de la norma frobenius debería funcionar bien?

Suresh Venkat

cuál es, por supuesto, la distancia de Hamming para matrices 0-1

Suresh Venkat

Tienes razón sobre la igualdad entre el cuadrado de la norma Frobenius y la distancia de Hamming. Me gustaría agregar que la distancia de Hamming dividida por es igual a la distancia de intercambio. Pero la pregunta era sobre la distancia de transposición ("Un intercambio se define como cambiar la posición de 2 elementos en la lista") y no sobre la distancia de intercambio. Lo que concierne a la norma espectral es que su cuadrado es igual a la distancia de intercambio.

2

$2$

Oleksandr Bondarenko

Oleksandr: ¿Entonces supongo que usted interpreta "intercambiar" como "intercambiar dos elementos adyacentes"?

Anthony Labarre