Algorithm - combine multiple lists, resulting in unique list and retaining order

Question

I want to combine multiple lists of items into a single list, retaining the overall order requirements. i.e.:

1: A C E
2: D E
3: B A D

result: B A C D E

above, starting with list 1, we have ACE, we then know that D must come before E, and from list 3, we know that B must come before A, and D must come after B and A.

If there are conflicting orderings, the first ordering should be used. i.e.

1: A C E
2: B D E
3: F D B

result: A C F B D E 

3 conflicts with 2 (B D vs D B), therefore requirements for 2 will be used.

If ordering requirements mean an item must come before or after another, it doesn't matter if it comes immediately before or after, or at the start or end of the list, as long as overall ordering is maintained.

This is being developed using VB.Net, so a LINQy solution (or any .Net solution) would be nice - otherwise pointers for an approach would be good.

Edit: Edited to make example 2 make sense (a last minute change had made it invalid)

Answer 1

The keyword you are probably interested in is "Topological sorting". The solution based on that would look as follows:

• Create an empty directed graph.
• Process sequences in order, for each two consecutive elements X,Y in a sequence add an edge X->Y to the graph, unless this would form a cycle.
• Perform a topological sort on the vertices of the graph. The resulting sequence should satisfy your requirements.