Algoritmo para obtener rápidamente una ordenación parcial a través de múltiples listas enlazadas

Question

Tengo una situación, como sigue:

• I tienen n listas enlazadas doblemente
• Cada lista ha de comenzar un centinela y terminar
• las listas tienen todos la misma principio y nodo final (no es necesario, pero por motivos de simplicidad)
• las listas son homogéneas y pueden compartir elementos

me gustaría encontrar una ordenación parcial de todos los nodos en todas las n listas, comenzando con el nodo comenzando y terminando con, así, el nodo de extremo, de tal manera que cualquier nodo que aparece en nx listas , donde x < n, se ordenarán con respecto a los otros nodos en todas las listas en las que aparece.

Utilización de matrices para proporcionar un conjunto de ejemplo de listas:

first = [a, b, d, f, h, i]; 
second = [a, b, c,  f, g, i]; 
third = [a,   e, f, g, h, i]; 

Obviamente, una respuesta posible sería [a, b, c, d, e, f, g, h, i], pero otro el orden admisible sería [a, b, d, e, c, f, g, h, i].

Sé que hay es un algoritmo rápido para hacer esto, ¿alguien recuerda cómo funciona o cómo se llama? Ya tengo algunas versiones lentas, pero estoy seguro de que en algún lugar de Knuth hay uno mucho más rápido.

(. Y, antes de preguntar, esto no es para la tarea o proyecto Euler, y no puedo hacer esto más concreto Este es el problema.)

Editar: Estoy relativamente seguro de que el parcial el orden se define solo mientras los puntos finales estén en todas las listas y en las mismas posiciones (comienzo y final). No me opondría a una búsqueda en tiempo lineal para encontrar esos puntos finales, y si no se pueden encontrar, entonces se podría generar un error allí.

Answer 1

Parece muy similar a Topological sort para mí. Hay varios algoritmos para obtener un estado ordenado topológicamente. El que particularmente me gusta es similar a una primera búsqueda de amplitud. Mantenga dos listas, uno de todos los nodos que no tienen bordes internos, digamos L (inicialmente solo el nodo a), y el otro con los nodos ordenados parcialmente, F.Ahora bien, en cada paso,

pick a node from `L`, 
do some operations (explained later), 
and move the chosen node to the `F` list. 

En el "paso de hacer algunas operaciones",

choose all successors of the source node which have exactly one in-link add them to L. 
Remove the link from the source node to all the successors in the previous step 

Ahora, la lista F tiene todos sus nodos topológicamente ordenados. Lamento la espantosa explicación, el enlace del wiki tiene buenos diagramas :)

Answer 2

O estoy malentendido, o el algoritmo de alienhard puede fallar. (Me gustaría añadir esto como un comentario, pero soy demasiado nuevo aquí para comentar.)

Considere este ejemplo:

first = [a, b, c, d,    i]; 
second = [a,  d, e, f,  i]; 
third = [a,    f, g, h, i]; 

algoritmo de Alienhard dará: a=0, b=1, c=2, d=3, e=2, f=3, g=2, h=3, i=4.

El algoritmo requiere que e sea anterior a d aunque e siga d en segundo.