We consider a permutation P = (p₁,…,p_n) of the range 1..n, e.g. P = (1,4,2,3,7,5,6).

A reversal P.r(i,j), with i<j, reverses the segment (p_i,…,p_j), e.g. P.r(3,5) = (1,4,7,3,2,5,6).

In the problem of sorting by reversals, we have to find a series of reversals that transforms a given permutation P into the identity permutation (1,2,…,n), such that the number of reversals needed is as small as possible.

It is proven that the algorithm below never uses more than 4 times the optimum number of reversals (see reference):

while P has breakpoints
    if P has a decreasing strip
        let k = the smallest element belonging to a decreasing strip
        reverse the segment between k and k-1
    else
        reverse the increasing strip with the smallest element 
                (different from 1 if 1 is already in the first position)

Assignment

Write a Python function reversalsort that takes a permutation as a parameter and that returns the number of reversals used by the above algorithm.

Examples

>>> reversalsort([1, 3, 2, 7, 6, 4, 5, 8])
3
>>> reversalsort([5, 2, 4, 8, 6, 1, 9, 7, 3])
7
>>> reversalsort([2, 1, 3, 4, 5, 8, 7, 6, 9])
2

References

• V. Fack, “Bioinformatics Algorithms” (lecture notes, p.31-34), 2019.