minimal swaps cyclic permutation

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

minimal swaps cyclic permutation

Post by temper_3243 »

hi,
how do we calculate the minimal number of swaps (arbitrary) required to sort a permutation which is cyclic. The permutation need to sorted in clockwise or anticlockwise direction.

This was a problem from iarcs and the contest is over.

2 5 1 4 3 -> requires 1 swap on ele 2 and 4 (or 1 and 5) which makes 4 5 1 2 3 (sorted) { 2 1 5 4 3 }

2 5 1 3 4 -> 2 swaps the length can be N <=5000

skinnyguy
New poster
Posts: 17
Joined: Fri Oct 22, 2004 3:41 pm

my way of solving this

Post by skinnyguy »

one way i could do this is
find the minimum number of swaps between the original sequence and the final sequence, where the final sequence maybe any one of the (2*N) possible sorted sequences.
the step for finding the minimum number of swaps takes O(N) time.. so this algorithm would be bounded O(N^2)

Post Reply

Return to “Algorithms”