2

This is one of the question from online written test.

Books numbered from (1...N) have arrived to a warehouse.

The books are said to be best arranged if a book “i” is present only to the left of book “i+1” (for all i, 1 <= i <= N-1) and that book N is present to the left of book 1. [Yes! Any cyclic sorted sequence is a best arrangement]

Books received are in a random order.Now your task is to find out the minimal number of moves required to achieve the best arrangement described above.

Note that only valid move is to choose a pair of adjacent books and have them switch places.

For Example if the books were initially in the order 3 5 4 2 1

Solution can be

a. First swap the second pair of books: { result : 3 4 5 2 1 }

b. Swap the rightmost pair: { result : 3 4 5 1 2 }

So, in 2 moves we achieve the best arrangement.

I tried but not able to find out solution for this.First I though that i will divide the array in two arrays and then I will apply insertion sort on both the arrays but that is also not working. Please help me to find out a algo for this question.

archit
  • 185
  • 4
  • 12
  • 2
    Duplicate of:http://stackoverflow.com/questions/15364607/given-an-array-of-integers-in-random-order-you-have-to-find-the-minimum-number-o – SidR Mar 13 '13 at 17:53
  • One of your classmates perhaps? – Pete Mar 13 '13 at 17:54
  • Isn't this condition "book “i” is present only to the left of book “i+1” (for all i, 1 <= i <= N-1) " violated in the answer 3,4,5,1,2 given in OP, as 2 is to right of 3. Or is this condition wrongly stated in OP – goldenmean Mar 15 '13 at 14:42
  • Possible duplicate of [given an array of integers in random order you have to find the minimum number of swaps to convert it to cyclic sorted array](https://stackoverflow.com/questions/15364607/given-an-array-of-integers-in-random-order-you-have-to-find-the-minimum-number-o) – xskxzr Mar 10 '18 at 04:18

1 Answers1

1

N,1 can be anywhere in the sequence. eg 1..5, could be 3,4,5,1,2. So the first digit could be 1..5, ie 5x as complicated as Previous question. So, you'll have to do it 5 times. Use a sort algorithm that has a replaceable compare function.

So for the 3rd test the compare would be:-

// returns <0, 0 or >0
int compare(a,b){
     return ((b+N-3)%N) - ((a+N-3)%N);
}
Community
  • 1
  • 1
QuentinUK
  • 2,997
  • 21
  • 20
  • If you want to do it properly then Google "Sorting circular permutations by bounded transpositions", this is a current research problem in Bioinformatics & Computational Biology but the papers are a bit advanced. – QuentinUK Mar 13 '13 at 18:48