Merging ordered List

Question

Please allow me to ask this question with an example: Suppose we have the following 3 lists (omitted double quotes for clarity):

L1: (a, c, b, d, f, j)
L2: (b, e, j, k)
L3: (a, d, e, g, h, j, i)

The output list can look like any of the following (there are more solutions)

Lanswer1: (a, c, b, d, e, f, g, h, j, i, k)
Lanswer2: (a, c, b, d, f, e, g, h, j, i, k)
Lanswer3: (a, c, b, d, e, f, g, h, j, k, i)

In summary, the resulting ordered set

• Contains the union of elements from all the lists
• Order of the elements in all the original lists are preserved.

A 4th list, L4: (b, c, d), when added to the input, should throw an exception (since c comes before b in L1)

I came up with the answers by inspection. Can anybody suggest an algorithm to do this? Thank you, - M.S.

Answer 1

This can be done using topological sorting.

First build the directed graph from the lists. The elements of the list become the nodes. The edges go from the first element to the second, from the second to the third, and so on.

Depending on how you implement the algorithm you can get all possible solutions, or just one. Also, If the graph contains a cycle then the algorithm will stop with an error.

This is how the graph from your lists would look like:

Source:

digraph {
  {
    edge [color = "red"]
    a -> c
    c -> b
    b -> d
    d -> f
    f -> j
  }
  {
    edge [color = "blue"]
    b -> e
    e -> j
    j -> k
  }
  {
    edge [color = "green"]
    a -> d
    d -> e
    e -> g
    g -> h
    h -> j
    j -> i
  }
}