Объедините два отсортированных списка и сохраните порядок

Question

Для двух списков, например,

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

Я хочу, чтобы результат сохранял порядок, заданный обоими входными списками, т.е.

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

Результат не уникален как "D" и " Y "также можно переключить (но если это не ясно, лексикографи c порядок должен разрешить конфликт) Также, если бы у меня было что-л. например,

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

позиции B или A должны обрабатываться взаимозаменяемо (т.е. не может быть создан уникальный порядок, а порядок B A должен рассматриваться как A = B), что приведет к к принятым результатам

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

(желательно как в детерминированном c лексикографическом c порядке A и B) или

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

Другими словами Я хочу комбинацию списков, чтобы сохранить порядок, если он уникален, а где нет, результат должен быть детерминированным c например, в соответствии с лексикографией c упорядочением.

Есть ли библиотека для python, которая выполняет это, или я бы придется реализовать это самостоятельно? Я посмотрел на OrderedDict и OrderedSet, но оба они не обрабатывают слияние, как я хочу.

Answer 1

Возможно, вы захотите использовать топологическую сортировку . Если вы не хотите реализовывать алгоритм с нуля, вы можете использовать пакет NetworkX Python:

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']

По сути, вы строите граф, в котором каждое направленное ребро из вершины u в вершину v означает, что u стоит перед v в порядке. В этом конкретном примере c "A" стоит перед "D", "D" стоит перед "B" и т. Д. c:

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