¿Cómo ordenar los objetos basados solo en relaciones "menos que"?

Question

Di que tengo n objetos, cada uno con un valor desconocido, y una Matrix Z. tal que Z (I, J)= 1 Si el valor del objeto I es menor que el valor del objeto J, y Z (i, j)= 0 de lo contrario.¿Cómo puedo ordenar estos objetos N, dado solo la Matriz Z?

Answer 1

Lo que está buscando es una Comparación Ordenar . Por favor, eche un vistazo a ese artículo.

---

Permítanos declarar claramente el requisito de cualquiera de los dos objetos dados, el objeto I y el objeto J cuando aparecen en la lista ordenada final. Objeto que debería ocurrir antes del objeto J IF Z (I, J)= 1. El objeto que puedo ocurrir antes o después del objeto J si Z (I, J)= Z (J, I)= 0.

Como se mencionó Vonbrand, deberíamos asumir que la matriz Z especifica una relación "menor que" bien definida o, en términos de matemáticas, un orden estricto total en los valores de los objetos. De lo contrario, los objetos dados pueden no ser ordenados.

• z [i, j]= 0 si z [j, i]= 1. De lo contrario, no podemos ordenar el objeto I y el objeto J.
• z [j, i]= 0 si z [i, k]= 1 y z [k, j]= 1 para algunos k. De lo contrario, no podemos ordenar el objeto I, J y K (Piense en el papel-tijeras-rock).

---

Supongamos que Z especifica una relación "menos que" bien definida. Luego, también define un " $ \ le $ " Operación de comparación naturalmente. A saber, si Z (J, i)= 0, entonces el objeto I $ \ le $ objeto j. Por lo tanto, podemos aplicar cualquier tipo de comparación para ordenar el objeto Dado $ n $ objeto.

Casi todos los algoritmos de clasificación son tipos de comparación. Por ejemplo, Quicksort, Mergesort, Ordenador de inserción, clasificación de selección y tipo de burbuja. Una notable excepción es contando ordenador .