arrays - 匹配三个排序列表的算法

Question

所以我已经尝试解决这个问题几个小时了，但显然仍然缺少一些东西。也许我想错了，但我认为这是一个非常复杂的问题:

我有三个列表，其中的项目按固定顺序排列。为了解释这个问题，假设它们包含项目 A 到 Z - 大多数情况下顺序相同，但有一些异常(exception)，其中项目可以位于不同的位置。也只有一个列表包含所有项目 - 另一个包含一个子集并且缺少某些项目。作为这个问题的解决方案就足够了，可能没有包含所有项目的列表，但只有部分重叠的集合。如果有一种算法可以解决多个(> 3 个)列表的问题，那就更好了。

举个例子:

List 1: A B C D E F G H I J
List 2: A C D B F G
List 3: B C D E H F G

现在我想要的是匹配这三个列表，以可视化排序顺序不同的地方以及缺少的项目。所以结果应该是:

List 1: A B C D   E   F G H I J
List 2: A   C D B     F G
List 3:   B C D   E H F G

所以我立即看到，List 2 的 B 位置错误，List 3 中缺少 A，而 H 的位置也错误。

我正在考虑将结果存储在 CSV 中以导入到 Excel 中。所以行是:

A,A,
B,,B
C,C,C
...

现在我的问题是:如何匹配列表以生成 CSV 输出？我使用的语言是Java。到目前为止，我没有解决以下问题，即引用列表以外的列表包含较早的项目，这些项目出现在引用列表中较晚。

顺便说一句，这是一个现实世界的问题。

如有任何建议，我们将不胜感激。

Answer 1

有现成的工具可以解决这个问题，例如 Unix 工具 diff3。尝试为任意数量的列表解决它是不可取的，除非您愿意投入大量时间来开发启发式方法，因为您随后正在处理 longest common subsequence problem 的 NP-hard 一般情况。 .