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

Question

我有两个包含相同项目和不同订单的列表。例如：

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

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

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

但是[2, 4]or[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

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

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