python - 从两个列表中删除最少的项目以使列表相同

Question

我有两个包含相同项目和不同顺序的列表。 例如:

a = [4, 2, 3, 1]
b = [2, 3, 1, 4]

我应该删除哪些项目以使列表相同？ 这里:[4] 是一个答案，所以:

a = [2, 3, 1]
b = [2, 3, 1]

但是 [2, 4] 或 [2, 3, 1] 也是答案，如果我删除 [2, 3, 1]:

a = [4]
b = [4]

我需要删除最少数量的元素，这里[4]是最优解。

另一个例子:

a = [1, 2, 3, 4]
b = [2, 1, 4, 3]

可能的答案:

[1, 3]
[1, 4]
[2, 3]
[2, 4]

算法的顺序并不重要。

Answer 1

我当然会首先搜索最长的公共(public)子序列(google LCS，许多算法可用，例如 algorithmist )，然后如果您从原始列表之一中删除 LCS 元素，您将获得最短的元素列表消除。在伪代码中:

lcs = LCS(a,b)
res = copy(a)
foreach element e in lcs
  remove(res,e)
return res