algorithm - 寻找最少的变换次数

Question

我需要一种算法来计算类似于 Levenshtein 距离的东西。它应该计算从一个序列到另一个序列的最小可能转换次数。允许的转换是删除、插入和移动:

删除 3:{1, 2, 3, 4} 之前，{1, 2, 4} 之后

插入 5:{1, 2, 3, 4} 之前，{1, 2, 5, 3, 4} 之后

4 步:{1, 2, 3, 4} 之前，{4, 1, 2, 3} 之后

因此，算法应该在给定数字的开始和结束序列的情况下计算此类转换的最小数量，并且理想情况下，给出所需转换的列表。序列的一个重要特征是数字永远不会重复。

我有一个想法，我可以修改 Levenshtein 算法，让它只计算删除和插入的次数，而忽略替换。并且移动次数将是删除次数加上插入次数除以 2。但我不确定它是否正确。

有人知道这样的算法吗？

编辑:

我可能应该说，该算法适用于一系列序列。例如:

{ {1, 2, 3}, {4}, {5, 6, 7} }

数字不重复的地方。序列中内部元素的总数不变。元素可以从一个内部序列迁移到另一个内部序列。内部序列的数量也是恒定的。所以可能是

{ {1, 2, 3, 4, 5, 6, 7}, {}, {}
{ {}, {1, 2, 3, 4, 5, 6, 7}, {} }
{ {}, {}, {1, 2, 3, 4, 5, 6, 7}

想法是计算每个对应的内部序列的距离，然后将它们相加得到外部序列的距离。
因此元素可以被删除或插入到内部序列中，但它们永远不会从外部序列中消失。

该算法最重要的方面是它应该找到MINIMAL 数量的转换。不仅仅是一些转换。

Answer 1

您可以跟踪删除和插入的数字，最后通过检查这两个集合以找到再次删除和插入的数字来计算移动次数:

moved = intersection(deleted, inserted)
moves = sizeof(moved)
deletions = sizeof(deleted) - sizeof(moved)
insertions = sizeof(inserted) - sizeof(moved)