Perdone si es una pregunta demasiado imprecisa. Mi habilidad matemática es débil, sólo soy un humilde programador.
Estoy buscando un algoritmo para ordenar una lista de elementos en base a un orden parcial: cada elemento tiene una lista de otros elementos que debe ser antes de y una lista de artículos que debe ser después de . Puedo producir a partir de esto una lista de aristas dirigidas, $A > B$ . Sin embargo, muchos pares no tendrán un orden determinado, mientras que otros sólo tendrán un orden implícito (es decir $A > B$ y $B > C$ implica $A > C$ pero tampoco $A$ ni $C$ especificar esto).
Lo que quiero obtener de esto es una única lista ordenada que contenga todas las entradas una vez, que satisfaga todas las condiciones. A menudo habrá muchas soluciones posibles para un conjunto dado de entradas, pero no necesito encontrarlas todas o un orden definitivo "mejor" (si es que eso tiene algún significado).
Preferiblemente el algoritmo será:
- Es estable ante pequeños cambios, por lo que la lista ordenada resultante no cambia bruscamente cuando cambia una entrada. Esto hará que el código sea más fácil de depurar en caso de que haya que cambiar una de las órdenes.
- Tiempo lineal o casi
- Funcional más que procedimental (pero no ligado a un único lenguaje de programación)
- Lo suficientemente claro como para que mi cabeza lo entienda
Ningún elemento puede aparecer más de una vez en las entradas. Por supuesto, es posible que las entradas no sean válidas, es decir, que el gráfico de aristas dirigidas sea cíclico. En este caso, lo mejor sería detectar el error e informarlo con precisión para ayudar a la depuración.
