En matemáticas discretas, esto se llama un orden parcial , que es un subconjunto de un orden total . En un orden parcial, debe ser posible comparar pares de elementos, de modo que todos los elementos de la secuencia tengan una relación menor que al menos con otro elemento. En base a esto, es posible formar una cadena , que es una secuencia en la que cada elemento tiene una relación menor que al menos un elemento con un índice más alto (espere el último elemento).
En ciencias de la computación, hay un método para crear la secuencia de cadena basada en la relación menor que, llamada ordenación topológica.
Un ejemplo de un problema que se puede resolver de esta manera: tiene una lista de personas y desea ordenarlas por edad. No conoce sus edades, pero se le da una lista de quién es mayor que quién, en la forma “X es mayor que Y”. Por simplicidad, nadie tiene la misma edad. Si A es más viejo que B y B es más viejo que C, entonces sabes que A es más viejo que C, ya que más viejo es una relación transitiva.
Suponiendo que no haya contradicciones (por ejemplo, A anterior a B, pero B anterior a A), esta lista de reglas conduce naturalmente a un gráfico acíclico dirigido , donde cada relación anterior es un borde dirigido. Si, después de agregar todas las reglas al gráfico, solo hay un componente conectado, entonces el problema es solucionable, simplemente ordénelos topológicamente y puede ordenarlos por edad. Si hay más de un componente conectado, hay varios grupos en los que sabe quién es mayor que quién, pero no puede ordenarlos a todos.
Un ejemplo de un problema que naturalmente tiene un orden total es la clasificación de números. Simplemente puede tomar el valor del número para comparar dos números cualquiera. Hay muchos algoritmos bien conocidos para resolver esto, algunos basados en la comparación por pares (clasificación de burbujas, clasificación rápida, etc.), algunos basados en el bucketing (clasificación de radix, clasificación de cubos) y algunos extraños también, como la clasificación bitónica.