计算将一个排列转换为另一个排列所需的相邻交换 [英] Counting the adjacent swaps required to convert one permutation into another

问题描述

我们给了两个小写拉丁字母序列。
它们的长度相同，且给定类型的字母
的数量相同（第一个字母的t与第二个字母的相等，因此
的字母相同）。我们需要找到交换到
所需的最小交换次数（交换是指将
更改为两个相邻 字母的顺序）从第一个序列到第二个序列。我们
可以安全地假设每两个序列可以相互转换
。我们可以用蛮力来做到这一点，但是序列太长了。

We're given two sequences of lowercase latin alphabet letters. They're both the same length and have the same amount of given types of letters (the first has an equal number of t's as the second and so on). We are required to find the minimum number of swaps (by "swap" we mean changing the order of two neighboring letters) required to transform the first sequence into the second. We can safely assume every two sequences CAN be transformed into each other. We could do this with brute-force, but the sequences are too long for that.

输入：

序列的长度（至少2个，最多999999个），然后是
，然后是两个序列。

Input:
The length of the sequences (at least 2, at most 999999) and then two sequences.

输出：

一个整数，表示
序列变为相同所需的交换次数。

Output:
An integer representing the number of swaps needed for the sequences to become the same.

示例：

{5，aaaaa，aaaaa}应该输出{0}，

{4，abcd，acdb}应该输出{2}。

Example:
{5, aaaaa, aaaaa} should output {0},
{4, abcd, acdb} should output {2}.

我想到的第一件事是冒泡。我们可以简单地对排序每个交换的序列进行冒泡排序。问题是：a）最坏的情况是O（n ^ 2）b）我不确信在每种情况下都会给我最小的数字...即使是优化的冒泡现象也似乎并不能解决问题。我们可以实施鸡尾酒解决方案来解决乌龟的问题-但这会给我带来最佳表现吗？也许有更简单/更快的方法？

The first thing that came to my mind was bubblesort. We can simply bubblesort the sequence counting each swap. The problem is: a) it's O(n^2) worst-case b) I'm not convinced it would give me the smallest number for every case... Even the optimized bubblesort doesn't seem to be doing the trick. We could implement the cocktail sort which would solve the problem with turtles - but will it give me the best performance? Or maybe there's something simpler/faster?

这个问题也可以表述为：当唯一允许的操作是时，如何确定两个字符串之间的编辑距离？

This question can also be phrased as: How can we determine the edit distance between two strings when the only operation allowed is transposition?

推荐答案

这是一个简单而有效的解决方案：

Here's a simple and efficient solution:

让 Q [s2 [i]] =位置字符s2 [i]在s2中处于打开状态。设 P [i] =第二个字符串中与s1 [i]对应的字符在什么位置。

建立Q和P：

for ( int i = 0; i < s1.size(); ++i )
    Q[ s2[i] ].push_back(i); // basically, Q is a vector [0 .. 25] of lists

temp[0 .. 25] = {0}
for ( int i = 0; i < s1.size(); ++i )
    P[i + 1] = 1 + Q[ s1[i] ][ temp[ s1[i] ]++ ];

示例：

    1234
s1: abcd
s2: acdb
Q: Q[a = 0] = {0}, Q[b = 1] = {3}, Q[c = 2] = {1}, Q[d = 3] = {2}
P: P[1] = 1, P[2] = 4 (because the b in s1 is on position 4 in s2), P[3] = 2
   P[4] = 3

P 具有 2 倒置（ 4 2 和 4 3 ），这就是答案。

P has 2 inversions (4 2 and 4 3), so this is the answer.

此解决方案是 O（ n log n），因为可以在<$ c $中完成构建 P 和 Q c> O（n）和合并排序可以计算 O（n log n）中的反转。

This solution is O(n log n) because building P and Q can be done in O(n) and merge sort can count inversions in O(n log n).

这篇关于计算将一个排列转换为另一个排列所需的相邻交换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！