logo标签列表

寻找最少的转换次数

algorithmmath
3
我需要一个算法，它可以计算类似于Levenshtein距离的东西。它应该计算从一个序列到另一个序列所需的最小变换数。允许进行的转换是删除、插入和移动：
删除3： before {1, 2, 3, 4}，after {1, 2, 4}
插入5： before {1, 2, 3, 4}，after {1, 2, 5, 3, 4}
移动4： before {1, 2, 3, 4}，after {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} }
这个算法的想法是计算每个对应内部序列的距离，然后将它们相加以得到外部序列的距离。
因此，元素可以从内部序列中删除或插入，但它们永远不会从外部序列中消失。
这个算法最重要的方面是它应该找到最小的变换次数，而不仅仅是一些变换次数。
移动 = 重新排列；做一些谷歌搜索，你会发现这是生物学中一个极其困难的问题。 - nlucaroni
5个回答
2
你可以追踪删除和插入的数字，并在最后通过检查这两个集合中被删除并再次插入的数字来计算移动次数：
moved = intersection(deleted, inserted)
moves = sizeof(moved)
deletions = sizeof(deleted) - sizeof(moved)
insertions = sizeof(inserted) - sizeof(moved)
1

由于您的列表仅包含唯一元素，因此很清楚您需要删除哪些元素以及插入哪些元素。剩下的问题是找到从一个列表开始到达另一个包含相同元素的列表所需的最小移动次数。始终可以重新标记两个列表中的元素，使得起始列表中的元素递增。

例如，我们可能会遇到以下问题：从列表开始查找最小移动次数

[1,2,3,4,5,6,7]

得到列表

[3,5,1,2,4,7,6].

为了解决这个问题，可以使用一个小技巧。与其尝试找到要移动的最小元素数量，不如找到不需要移动的最大元素数量。这些必须是第二个列表中按递增顺序排列的元素。这就是最长递增子序列问题。在上面的例子中，1、2、4、7将是一个最大子集。因此，要移动的最小元素集将是{3,5,6}。

请问您能否解释一下“始终可以重新标记两个列表中的元素，使得起始列表中的元素是递增的”是什么意思？如果输入为[3,1,5,2,4]，输出为[3,1,4,5,2]，则这两个序列都没有任何顺序。 - user1071840
0

考虑：

abc

被转换为：

abcdef

这是3个插入，0个删除和0个移动。但是，您的算法将给出3个插入，0个删除和1.5个移动。

实际上，它会给出3作为答案。这可以解释为3次插入、3次删除或1.5次移动。算法返回的数字是序列之间的距离，因此它是衡量它们彼此之间有多远的一种度量。记住这一点，我为不同的操作分配了不同的成本。删除和插入的成本为1，移动的成本为2。 - Max
0

让我们看看我是否正确理解了您的问题：您已经给出了一个序列X，其中包含1到n中的每个数字恰好在一个（内部）序列中。使用仅两种类型的操作，您必须将X转换为另一个给定的相同类型的序列Y，在转换中要尽量减少所需的操作次数。

第一种操作是将数字从任何位置移动到同一内部序列中的任何其他位置。第二种操作是将数字从一个内部序列中的任何位置移动到另一个内部序列中的任何位置。

这是您的问题吗？如果是，请继续阅读。

解决此问题的通用方法是考虑由取X和Y作为顶点集的相同类型的所有序列组成的无序图。当且仅当它们可以使用两种允许的操作之一精确地转换为彼此时（此关系是对称的，因为您可以通过另一个允许的操作来撤消允许的操作），两个顶点在图中由边连接。现在使用最短路径查找算法，例如breadth first search，其中您动态生成邻居。

由于可达顶点数量随着所需步数的增加呈指数级增长，因此在实践中，您应该交替从起点X和起点Y运行算法。当确定了1、2、3、...步内可到达的所有顶点时，您可以切换起点，并在从X rsp开始可达的点集与从Y开始可达的点集相交时停止。

对于这个通用算法，运行时间和内存使用率甚至对于适度的n来说都太高了，但是可以使用两个观察结果进行极大优化：

  • 已经从一开始包含在正确序列中的元素可以使用第一个操作独立于所有其他元素（即包含在其他内部序列中或必须移动到另一个内部序列中的元素）进行重新排序。

  • 通过第二个操作从一个内部序列移动到另一个内部序列的元素可以直接放置在正确的内部序列中的正确位置，以便它们不必再次被另一个操作移动。

由于内部序列的排序和元素在内部序列之间的移动都是独立的，因此操作总数是将内部序列排序的最小数量之和（仅考虑X和Y的相同内部序列中的元素）加上必须从一个内部序列移动到另一个内部序列的元素数量。

要确定已经正确包含在内部序列中的元素的（第一次）操作数量，只需忽略（取消）必须移动到另一个内部序列的元素。然后，对于由不需要移动的元素组成的序列集合作为图的顶点，使用上述通用方法描述的方法。如果移动一个元素（即应用第一个操作）将一个顶点（=序列）转换为另一个顶点，则图中存在两个连接的顶点。

0

我认为可以简化为以下步骤：

  1. 忽略不属于这个序列的元素，将属于这个序列的元素重新排列到正确的顺序。这是一个简单但不寻常的排序问题。
  2. 删除不需要的元素。
  3. 插入缺失的元素（放在正确的位置）。

最小化第一步是棘手的部分；对于我来说，如何证明给定的移动序列是最小的并不明显。但是，由于您似乎不关心计算成本，因此您可以做类似于蛮力搜索的事情（使用快速排序作为上限）。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接