¿Es posible usar un algoritmo de clasificación con una comparación no transitiva, y en caso afirmativo, ¿por qué se enumera la transitividad como un requisito para ordenar comparadores?
Antecedentes:
Un algoritmo de clasificación generalmente ordena los elementos de una lista de acuerdo con una función de comparación C (x, y), con
Los requisitos para este comparador son, hasta donde yo entiendo:
- reflexivo:
- antisimétrico:
- transitivo:
- C (x, y) se define para todas las x e y, y los resultados dependen solo de x e y
(Estos requisitos siempre se enumeran de manera diferente en las diferentes implementaciones, por lo que no estoy seguro de haberlos hecho bien)
Ahora me pregunto acerca de una función de comparación "tolerante", que acepta los números x, y como similares si : C ( x , y ) = { - 1 si x < y - 1 0 si | x - y | ≤ 1 + 1 si x > y + 1
Ejemplos: ambos [ 1, 2, 3, 4, 5]
y [1, 4, 3, 2, 5]
están correctamente ordenados en orden ascendente de acuerdo con el comparador tolerante ( si x aparece antes que y en la lista)
pero no lo es, ya que C (4,2) = 1[1, 4, 2, 3, 5]
Este comparador tolerante es reflexivo y antisimétrico, pero no transitivo.
es decir, C (1,2) = 0, c (2,3) = 0, pero C (1,3) = -1, violando la transitividad
Sin embargo, no puedo pensar en ningún algoritmo de clasificación que no produzca una salida "correctamente ordenada" cuando se le da este comparador y una lista aleatoria.
Por lo tanto, ¿no se requiere transitividad en este caso? ¿Y hay una versión menos estricta de transitividad que se requiere para que la clasificación funcione?
Preguntas relacionadas:
- ¿Por qué es necesaria la antisimetría para la clasificación comparativa? (sobre antisimetría)
- Algoritmos de clasificación que aceptan un comparador aleatorio (sobre un C aleatorio (x, y))
- OrderBy con un IComparer no transitivo (sobre el algoritmo de clasificación de C #, por mí)
fuente
Respuestas:
Usted preguntó: ¿Podemos ejecutar un algoritmo de clasificación, alimentándolo con un comparador no transitivo?
La respuesta: por supuesto. Puede ejecutar cualquier algoritmo con cualquier entrada.
Sin embargo, conoces la regla: basura en la basura, basura en la basura. Si ejecuta un algoritmo de clasificación con un comparador no transitivo, puede obtener resultados sin sentido. En particular, no hay garantía de que la salida se "clasifique" según su comparador. Por lo tanto, ejecutar un algoritmo de clasificación con un comparador no transitivo probablemente no sea útil de la manera que probablemente esperaba.
fuente
Dado un conjunto de elementos y una relación de ordenamiento binario, se requiere transitividad para ordenar totalmente los elementos. De hecho, la transitividad incluso se requiere para definir un orden parcial en los elementos. http://en.m.wikipedia.org/wiki/Total_order
Necesitaría una definición mucho más amplia de lo que significa "ordenado" para ordenar elementos sin transitividad. Es difícil ser autoconsistente. Otra respuesta dice "En particular, no hay garantía de que la salida se 'clasifique' de acuerdo con su comparador". Pero en realidad podemos decir algo mucho más fuerte. Le garantizamos que la salida no está ordenada según su comparador.
fuente
Parece que lo que desea es organizar elementos de manera que todas las clasificaciones discernibles sean correctas, pero los elementos que están cerca podrían considerarse "indistinguibles". Es posible diseñar algoritmos de clasificación que funcionen con tales comparaciones, pero a menos que haya límites para cuántas comparaciones pueden informar que las cosas son indistinguibles, no hay forma de evitar que requieran N (N-1) / 2 comparaciones. Para entender por qué, elija algún número N y cualquier algoritmo de clasificación que haga menos que N (N-1) / 2 comparaciones. Luego, complete una lista L [0..N-1], establezca cada elemento L [I] en I / N y "ordénelo" utilizando su comparador (el valor mínimo será 0 y el máximo (N-1) / N , entonces la diferencia será (N-1) / N, que es menor que 1).
Debido a que hay N (N-1) / 2 pares de elementos que podrían compararse, y el tipo no hizo tantas comparaciones, debe haber algún par de elementos que no se compararon directamente entre sí. Reemplace cualquiera de estos que se ordenó primero por 1 y el otro por -1 / N, revierta todos los elementos a su posición inicial y repita la operación de clasificación. Cada operación de comparación individual producirá cero, tal como lo hizo la primera vez, por lo que se realizarán las mismas comparaciones y los elementos terminarán en la misma secuencia. Para que la lista se ordene correctamente, el "1" tendría que ordenar después del "-1 / N" (ya que difieren en más de uno) pero dado que el algoritmo de ordenación nunca compararía esos dos elementos directamente uno contra el otro, no tendría forma de saber eso.
fuente
Rellene una matriz de n elementos con los valores n, n-1, n-2, ..., 2, 1. Luego intente ordenar utilizando el algoritmo de "inserción directa". Encontrará que cada elemento se considera igual al elemento justo antes y, por lo tanto, no se mueve. El resultado de la "clasificación" es la misma matriz.
fuente