Cyclic Strings

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 !!

Comments

  1. Pratik Poddar12:03 AM, November 08, 2009

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

    ReplyDelete
  2. Unknown2:06 AM, September 08, 2010

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

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more