假设问题是保持尽可能多的常见项目的相同相对顺序。
考虑图的节点表示m, n相应列表中具有相同值的索引对。例如 [a, b, c] 和 [b, a, c] => [(0, 1), (1, 0), (2, 2)]
两个节点的相对顺序m, n和m', n'可以满足当且仅当(m < m' and n < n') or (m > m' and n > n')。在前面的示例(0, 1), (1, 0)中，不满足此条件，因此不可能满足两个列表中a和的相对顺序。b而(1, 0), (2, 2)满足这个性质，因此可以保持 和 的a顺序c。
基于这个条件，找到所有节点对之间的边O(n^2)。要找到最佳排列，请使用 Bron-Kerbosch 算法找到最大的最大团（即 NP-complete ）。O(3^(n/3))生成的相同值索引对可用作生成合并列表的锚点。
如果多项式解决方案可以接受近似排序，则以下方法使用联合查找（具有路径压缩和秩优化）来近似最大团并O(n^2)及时运行并占用O(n)空间。
from collections import defaultdict
def find(cur, d):
path = []
while d[cur] != cur:
path.append(cur)
cur = d[cur]
for n in path:
d[n] = cur
return cur
def f(o, n):
if o == n:
return o
first_list = list(reversed(o))
second_list = list(reversed(n))
first_list_dict = {v: i for i, v in enumerate(first_list)}
common = []
for i, v in enumerate(second_list):
if v in first_list_dict:
common.append((first_list_dict[v], i))
if not common:
o.extend(n)
return o
if len(common) == len(first_list):
return list({v: None for l in (o, n) for v in l})
if len(common) == len(second_list):
return o
d = {p:p for p in common}
rank = defaultdict(int)
for i, p1 in enumerate(common):
for p2 in common[i+1:]:
if (p1[0] - p2[0]) * (p1[1] - p2[1]) > 0:
h1, h2 = find(p1, d), find(p2, d)
if rank[h1] > rank[h2]:
h1, h2 = h2, h1
elif rank[h1] == rank[h2]:
rank[h2] += 1
d[h1] = h2
freq = defaultdict(list)
for p in common:
freq[find(p, d)].append(p)
largest_clique = sorted(max(freq.values(), key=len))
res = []
seen = set()
l_idx1, l_idx2 = 0, 0
while largest_clique:
idx1, idx2 = largest_clique.pop()
new = first_list[l_idx1-1:idx1:-1]
new.extend(second_list[l_idx2-1:idx2:-1])
new.append(first_list[idx1])
res.extend(v for v in new if v not in seen)
seen.update(new)
l_idx1, l_idx2 = idx1, idx2
return res
for o, n in (
[[0, 1, 2, 3, 4, 5], [5, 0, 1, 3, 4]],
[[0, 1, 2, 3, 4, 5], [7, 3, 1, 2, 4, 5]],
[[0, 1, 2, 3, 4, 5], [3, 4, 5, 0, 1, 2]],
[["A", "B", "C", "E"], ["A", "D", "E"]],
[["A", "B", "D", "F", "G", "H"], ["A", "C", "D", "E", "F", "H"]],
[[0, 1, 2, 3, 4], [5, 6, 7, 8]],
):
print(f"{str(o): <30}, {str(n): <30} => {str(f(o, n)): >40}")
给出：
[0, 1, 2, 3, 4, 5] , [5, 0, 1, 3, 4] => [0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5] , [7, 3, 1, 2, 4, 5] => [0, 7, 3, 1, 2, 4, 5]
[0, 1, 2, 3, 4, 5] , [3, 4, 5, 0, 1, 2] => [0, 1, 2, 3, 4, 5]
['A', 'B', 'C', 'E'] , ['A', 'D', 'E'] => ['A', 'B', 'C', 'D', 'E']
['A', 'B', 'D', 'F', 'G', 'H'], ['A', 'C', 'D', 'E', 'F', 'H'] => ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
[0, 1, 2, 3, 4] , [5, 6, 7, 8] => [0, 1, 2, 3, 4, 5, 6, 7, 8]