Merge two sorted lists and preserve order

user_3456323 0
Viewed 177

Given two lists e.g.

l1 = ["A","D","B","C"]
l2 = ["X","A","Y","B"]

I want the result to preserve the order given by both input lists i.e. 

["X","A","D","Y","B","C"]

The result is not unique as "D" and "Y" could also be switched (but if it is not clear lexicographic order should handle the conflict) Also if I had smth. like

l1 = ["B","A"]
l2 = ["X","A","Y","B"]

positions of either B or A should be treated interchangeably (i.e. no unique order can be constructed and the order of B< A and B> A should be treated as A=B) which would lead to accepted results

["X","A","Y","B"]

(preferably as it is in deterministic lexicographic order of A and B) or 

["X","B","Y","A"]

Put in another way I want the combination of lists to preserve the order where unique and where it's not, the result should be deterministic e.g. according to lexicographic ordering.

Is there a library for python that accomplishes that or would I have to implement it on my own? I looked at OrderedDict and OrderedSet but both do not handle the merge as I want.

algorithm python
1 Answers

You might want to use to use topological sorting. If you don't want to implement the algorithm from scratch, you can use the NetworkX Python package:

from itertools import chain
from networkx import DiGraph, topological_sort

l1 = ["A", "D", "B", "C"]
l2 = ["X", "A", "Y", "B"]

# Build the graph
G = DiGraph(chain(zip(l1[:-1], l1[1:]), zip(l2[:-1], l2[1:])))

# Return a list of nodes in topological sort order
result = list(topological_sort(G))

# result: ['X', 'A', 'Y', 'D', 'B', 'C']

Basically, you build a graph where every directed edge from vertex u to vertex v implies that u comes before v in the ordering. In this specific example, "A" comes before "D", "D" comes before "B" etc:

>>> G.edges
[('A', 'D'), ('A', 'Y'), ('D', 'B'), ('B', 'C'), ('X', 'A'), ('Y', 'B')]
user_52961060
Related