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?

Answer 1

Regarding the minimum number of (not necessarily adjacent) swaps needed to convert a permutation into another, the metric you should use is the Cayley distance which is essentially the size of the permutation - the number of cycles.

Counting the number of cycles in a permutation is a quite trivial issue. A simple example. Suppose permutation 521634.

If you check the first position, you have 5, in the 5th you have 3 and in the 3rd you have 1, closing the first cycle. 2 is in the 2nd position, so it make a cycle itself and 4 and 6 make the last cycle (4 is in the 6th position and 6 in the 4th). If you want to convert this permutation in the identity permutation (with the minimum number of swaps), you need to reorder each cycle independently. The total number of swaps is the length of the permutation (6) minus the number of cycles (3).

Given any two permutations, the distance between them is equivalent to the distance between the composition of the first with the inverse of the second and the identity (computed as explained above). Therefore, the only thing you need to do is composing the first permutation and the inverse of the second and count the number of cycles in the result. All these operations are O(n), so you can get the minimum number of swaps in linear time.

Answer 2

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