Found it in collection of Jian Li, CS Department, University of Maryland

Given 2 cyclic strings, both consisting n distinct letter,namely a permuatation of 1 to n.

the problem is to find a rotation of one string that minimize the swap distance.(i.e.the number of swaps of adjacent elements to bring one necklace to the other)

Can you give an O(nlogn) algorithm?

This is a difficult problem. So, think hard!!

Update (11/12/09): Solution in comments !!

Step1: Realise that this problem can be converted into a simpler problem. By renumbering the numbers, I can always convert the problem to an equivalent problem where find the number of rotations such that the number of adjacent swaps required is minimum...

ReplyDeleteAlso note that no. of adjacent swaps is number of moves required in bubble sorting method. This is equivalent to calculating the number of inversion pairs in an n-length array.

Step2: The plan is to first calculate number of inversion pairs initially in O(nlog n). Then corresponding to each rotation, with O(nlog n) preprocessing time, we can find the number of inversion pairs in O(1). So, this is O(n logn) + O(n). Finding the minimum is O(1). So, the algorithm is O(nlog n)

Done in many advanced algorithms courses, this problem can be solved by using divide and conquer in O(n log n).

This makes use of calculating the number of inversion pairs in two halves independently. "Conquering" is done by calculating the number of inversion pairs with left end in left part and right end in right part. This can be calculated and is a byproduct of merge sort algorithm. We get an O(n log n) algorithm to calculate the number of swaps.

Now left is to give an algorithm to calculate number of inversion pairs in Permutation P2 from number of inversion pairs in Permutation P1, where P1 on cyclic rotation gives P2. Note that the only difference the two have is that the first number has moved to last. So, if we know the rank of the number in a sorted list, we can get it in O(1). Thats the O(n logn) preprocessing time we talked about. :)

So, answer.

Anyone can write it in a better way? Thanx

Here, you have not considered that we can swap the first and last element. In that case, number of swaps required can be lesser than the number of inversions.

ReplyDeleteeg. has 2n-2 inversions but by a single swap of n and 1, we get the correct permutation. I think the method of inversion pairs cannot be used in the above scenario.