Para resolver este problema, o colega escreveu na lousa a permutação. Então, a cada passo, sublinhou os dois blocos que seriam transpostos, e depois anotou a permutação resultante. Para verificar o número de breakpoints retirado por passo, estes foram representados como pontos que antecedem aos elementos da permutação e contados em cada uma das permutações (números da primeira coluna da tabela).
Segue a transcrição da lousa:
| 9 | .5.1.7.2.8.4.3.6. |
| 7 | .5.1 2.7 8.4.3.6. |
| 5 | .5.1 2.4.3.6 7 8 |
| 3 | .5.1 2 3 4.6 7 8 |
| 0 | 1 2 3 4 5 6 7 8 |
Com o intuito de descobrir se haveria alguma forma de ordenação em menor número de passos, foi utilizada a seguinte desigualdade:
d >= (n + 1 - c) / 2;
sendo d a distância, n o número de elementos da permutação e c o número de ciclos.
O número de elementos é 8, e o número de ciclos foi encontrado utilizando-se grafos de ciclos da permutação, como a imagem a seguir representa:
Logo, o número de ciclos é 1.
A distância é, então:
d >= (8 + 1 - 1) / 2 = 4
O limite inferior é quatro, ou seja, não há ordenação para a permutação com menor número de passos. Logo, a resolução apresentada pelo colega está correta.