计数将一种置换成另一种所需的掉期交易 [英] Counting the swaps required to convert one permutation into another
问题描述
我们正在给予的小写拉丁字母字母两个序列。 他们都具有相同的长度，并具有给定类型的相同量 的字母（在第一有相等数目的叔的作为第二等 上）。我们需要找到互换的最小数目（由交换我们的意思是改变 的两个相邻的信所需的顺序） 变换第一序列到第二。我们 可以安全地假设每两个序列可被转化 相互转化。我们可以用蛮力做到这一点，但序列是太长了。
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.
输出：
再$ P $的整数psenting所需交换的数量
序列变得相同。
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}.
这是来到我的脑海里的第一件事就是冒泡。我们可以简单地冒泡排序的顺序计算每个交换。现在的问题是：1）它是为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 和问：可以在
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屋！
