How to find minimum number of switches to sort a given permutation(let's say 1-10) in ascending order

user_11708288 0
Viewed 955

King Arthur has a shelf with 10 books, numbered 1,2,3,...,10. Over the years, the volumes got disordered. Arthur tries to order the books in the increasing order by exchanging positions of two books at once. Since the books are heavy, he can only switch two volumes each day. Help Merlin to order the books.

E.g If a permutation is 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 then we need just 5 switches to sort it in ascending order

Note: in the worst case there will be 9 switches

Q1. Find the permutation corresponding to the worst case

Q2. How to find the minimum number of switches required for a given permutation. (Algorithm & if possible code in either of C, C++, python)

PS: I was able to solve it manually, better say Trial N error ( Answer to Q1. 10, 1, 2, 3, 4, 5, 6, 7, 8, 9). but I wish to know the algorithm

permutation discrete-mathematics python-3.x sorting algorithm
2 Answers

Using a 1-indexed list,

Taking a list containing the same elements in an example given in the question:

[0,10,9,8,7,6,5,4,3,2,1] # Added 0 in front to make list 1-indexed

Step1: take the last index of the list... as an iterator

Step2: Running a while loop until the iterator value is greater than 0

Step3: If the element at the iterator matches to the value, then we have to decrement the value of the iterator as no need to perform swap operation.

Step4: If the element doesn't match, then swap the element with its index's value and increment the count of operations by 1. There is no need to decrement the iterator value as it might be a case that the value we got at the iterator's position might not be matching with its index...

Time Complexity of the Solution is O(2*N) ~~ O(N).

arr = [0,10, 1, 2, 3, 4, 5, 6, 7, 8, 9]
iterator = 10
count_of_operations = 0
while(iterator>0):
    index_to_swap = arr[iterator]
    if(index_to_swap == iterator):
        iterator = iterator - 1
    else:
        arr[iterator],arr[index_to_swap] = arr[index_to_swap],arr[iterator]
        count_of_operations = count_of_operations + 1
        
print(count_of_operations)
user_136519780

The minimum number of swaps needed equals the total number of elements subtracted by the number of permutation cycles. The worst case would seem to be one cycle. We can get a permutation for it by shifting the natural order down or up once (e.g., 1 2 3 -> 2 3 1 or 3 1 2).

For example:

1 2 3 4 5
2 5 4 3 1

Start with 1 and follow the cycle:
1 down to 2, 2 down to 5, 5 down to 1.

1 -> 2 -> 5 -> 1
3 -> 4 -> 3

We would need to swap index 1 with 5, then index 5 with 2; as well as index 3 with index 4. Altogether 3 swaps or n - 2.

We subtract n by the number of cycles since cycle elements together total n and each cycle represents a swap less than the number of elements in it.

For example:

 1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

1 -> 10 -> 1
2 -> 9 -> 2
3 -> 8 -> 8
4 -> 7 -> 4
5 -> 6 -> 5

Permutation cycles:

(10 1)(9 2)(8 3)(7 4)(6 5)

Q1 = num_elements - num_cycles
   = 10 - 5
   = 5

To get the worst case (Q2), shift the natural order down or up once. For example, a shift of 1 down:

1  2  3  4  5  6  7  8  9 10
2  3  4  5  6  7  8  9 10  1

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 1

Permutation cycles (just one):

(2 3 4 5 6 7 8 9 10 1)

Or a shift of 1 up:

 1  2  3  4  5  6  7  8  9 10
10  1  2  3  4  5  6  7  8  9

1 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Permutation cycles (just one):

(10 9 8 7 6 5 4 3 2 1)

Result:

Q2 = num_elements - num_cycles
   = 10 - 1
   = 9
user_20347870
Related