algorithm - Counting the adjacent swaps required to convert one permutation into another

Question

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.

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.

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

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?

question from:https://stackoverflow.com/questions/7797540/counting-the-adjacent-swaps-required-to-convert-one-permutation-into-another

Answer 1

Here's a simple and efficient solution:

Let Q[ s2[i] ] = the positions character s2[i] is on in s2. Let P[i] = on what position is the character corresponding to s1[i] in the second string.

To build Q and 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] ]++ ];

Example:

    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 has 2 inversions (4 2 and 4 3), so this is the answer.

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).