Resumo
Considere um vetor contendo os número de 1 a n em uma ordem qualquer. Uma transposição de prefixo é uma operação que troca de posição de dois blocos adjacentes, sendo que um ocupa as posições de 1 a y-1 (um prefixo) e o outro de y a z-1, para certos inteiros y e z tais que 1 < y < z <= n+1. O problema da ordenação por transposições de prefixo consiste em determinar, dado um vetor…