string - 是否有一种有效的算法来找到具有最差交换距离的给定字符串的排列？

Question

鉴于问题 Counting the adjacent swaps required to convert one permutation into another 中定义的交换距离(即，我们有一个字符串，并且该字符串的排列的交换距离是返回到原始字符串所需的“相邻字符交换”的最小数量)。

我想要一种算法来找到给定字符串的最大可能交换距离。当然，我们可以枚举所有排列并检查每个排列的交换距离，但这是非常低效的。有没有更快的方法？

Answer 1

允许您执行的基本操作是交换字符串的两个元素。这也是您在 insertion sort 中唯一可以执行的操作。 ，所以看来您可以从排序文献中提取行之有效的结果来解决问题。

根据插入排序的维基页面，最坏的情况是输入顺序相反。按照同样的逻辑，反转目标字符串应该会产生一个距离目标最远的字符串。

题为“On Generation Worst-Cases for the Insertion Sort”的论文 ( link ) 可能会有所帮助。