Levenstein转置距离

Question

如何使用动态编程实现转置/交换/旋转/交换距离。我必须强调，我不想检查其他操作（即复制，删除，插入，杀死等）只是转置/交换。

我希望将Levenstein算法应用于交换距离。代码如何看起来像？

Answer 1

我不确定在这种情况下可以使用Levenstein算法。如果没有插入或删除操作，则只能在具有相同长度和相同字符的字符串之间定义距离。字符串这是不可能的例子转换到相同的字符串，只有换位：

AB, ABC 
AAB, ABB 

就这样，算法可以找到未在两个字符串同一个地方的字符位置的所有可能的排列和寻找一个这可以用最少数量的换位或互换来表示。

Answer 2

动态规划的高效应用通常需要将任务分解为相同任务的多个实例以实现较短的输入。在Levenstein距离的情况下，这归结为两个字符串的前缀以及从一个字符串到另一个字符串所需的编辑次数。我不明白你的情况如何能够达到这样的分解。至少我没有看到会导致多项式时间算法的结果。

此外，您所说的操作并不十分清楚。取决于上下文，交换或交换可以意味着与转置相同的东西或用任意其他字母代替字母，例如， test->text。如果通过“转置/交换/旋转/交换”，你试图说只是“转置”，比你应该看看Counting the adjacent swaps required to convert one permutation into another。如果没有，请澄清这个问题。