Larry’s array
Problem statement
Larry has been given a permutation of a sequence of natural numbers incrementing from 1, as an array. He must determine if the array can be sorted using the following operation any number of times (Choose 3 indexes):
ABC → BCA → CAB → ABC
Inversion
Well there is a concept in discrete mathematics that I cannot fully understand. But I can understand enough to actually use it in the algorithm: Inversion.
An inversion is when a smaller element is to the right of a larger element. For example, in the array [1, 3, 2], the inversions are (1, 3) and (1, 2).
“What’s an interesting property of the inversion number is that the order of the permutation won’t actually affect its even/odd nature for the entire array”
If the number of inversions are even we can fully assert that they array can be sorted.
Otherwise (the number of inversions are odd), the array cannot be sorted. Having this into account, let’s take advantage of this concept 😊.
The algorithm
So instead of perform every rotation to find out if the array could be sorted, let’s use inversion.
- Loop over the array until we found a element in the wrong position
- Find the first element that is in correct position
- Perform inversions until j > i (Increasing the counter each time)
- Finally check if the number of inversions are even or odd
