Reconstructing Evolutionary Historiesclick to expand

When we calculate the Hamming distance between two genetic strings, we can easily infer a collection of point mutations that occurred on the evolutionary path between the two strings by simply examining the mismatched symbols. However, when calculating the reversal distance (see “Reversal Distance”), we only have the minimum number of reversals separating two permutations.

The computational problem of sorting by reversals demands instead that we provide a minimum list of reversals transforming one permutation into another. As a result, sorting by reversals subsumes the calculation of reversal distance: once we have a minimum collection of reversals, the reversal distance follows immediately.

Problem

A reversal of a permutation can be encoded by the two indices at the endpoints of the interval that it inverts; for example, the reversal that transforms $(4, 1, 2, 6, 3, 5)$ into $(4, 1, 3, 6, 2, 5)$ is encoded by $[3, 5]$.

A collection of reversals sorts $\pi$ into $\gamma$ if the collection contains $d_{\textrm{rev}}(\pi, \gamma)$ reversals, which when successively applied to $\pi$ yield $\gamma$.

Given: Two permutations $\pi$ and $\gamma$, each of length 10.

Return: The reversal distance $d_{\textrm{rev}}(\pi, \gamma)$, followed by a collection of reversals sorting $\pi$ into $\gamma$. If multiple collections of such reversals exist, you may return any one.

Sample Dataset

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

Sample Output

2
4 9
2 5