找到一个最小的转换数
我需要一个计算类似Levenshtein距离的算法。它应该计算从一个序列到另一个序列的最小可能的转换数。允许的转换是删除、插入和移动：
删除3:在{1，2，3，4}之前，在{1，2，4}之后
在{1，2，3，4}之前插入5，在{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}
其思想是计算每个对应的内部序列的距离，然后对它们进行求和，得到外部序列的距离。
因此，元素可以被删除或插入到内部序列中，但它们永远不会从外部序列中消失。
该算法最重要的方面是它应该找到最小数的转换。不仅仅是一些变体。
回答 5
Stack Overflow用户
发布于 2009-09-08 19:41:58
由于您的列表只包含唯一的元素，因此很清楚您必须删除哪些元素，以及必须插入哪些元素。剩下的问题是找到最小数量的移动，从一个列表开始，得到另一个包含相同元素的列表。总是有可能重新命名这两个列表中的元素，从而使凝视列表中的元素不断增加。
我们可能会找到从列表开始的最小移动次数的问题
1,2,3,4,5,6,7
这就给出了清单
3,5,1,2,4,7,6
要解决这个问题，我们可以用一些小把戏。与其试图找到要移动的最小数量的元素，更容易找到不需要移动的最大数量的元素。这些必须是第二个列表中按递增顺序排列的元素。这是最长增长子序列问题。例如，在上面的例子中，1,2,4,7将是一个最大子集。因此，可以移动的一组最小元素是{3,5,6}。
Stack Overflow用户
发布于 2009-09-08 02:11:33
您可以跟踪已删除和插入的数字，并在最后通过检查这两组以查找已删除和再次插入的数字来计算移动次数：
moved = intersection(deleted, inserted)
moves = sizeof(moved)
deletions = sizeof(deleted) - sizeof(moved)
insertions = sizeof(inserted) - sizeof(moved)Stack Overflow用户
发布于 2009-09-08 01:29:47
考虑：
abc它被转化为：
abcdef这是3次插入，0次删除，0次移动。但是，您的算法将提供3次插入、0次删除和1.5次移动。
https://stackoverflow.com/questions/1391538
复制相似问题
腾讯云开发者
