计算将一种排列转换为另一种排列所需的相邻交换 [英] 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)，因为构建P和Q可以在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屋！