2

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

我有三个列表，其中的项目按固定顺序排列。为了解释问题，假设它们包含项目 A 到 Z - 大部分顺序相同，但有一些例外，项目可以位于不同的位置。此外，只有一个列表包含所有项目 - 另一个包含一个子集并且缺少某些项目。由于此问题的解决方案就足够了，因此可能没有包含所有项目的列表，而只有部分重叠的集合。更好的是解决多个（> 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

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

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

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

现在我的问题是：如何匹配列表以生成 CSV 输出？我使用的语言是 Java。到目前为止，我未能解决除参考列表之外的列表包含较早项目的问题，这些项目稍后出现在参考列表中。

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

任何建议表示赞赏。

4

2 回答 2

3

有现成的工具可以解决这个问题，例如 Unix 工具diff3。除非您愿意投入大量时间开发启发式算法，否则不建议尝试解决任意数量的列表，因为您正在处理最长公共子序列问题的 NP-hard 一般情况。

于 2013-02-01T11:44:42.483 回答
1

如果我正确理解了您的问题，那么您实际上是在尝试解决多序列比对问题，这是生物信息学中经过充分研究的主题。有几种算法，其中一些基于Levenshtein 距离的概念（这将解决你的问题的两个数组版本） - 我建议你从那里开始。

于 2013-02-01T11:48:21.410 回答