Минимальное количество транспозиций для сортировки списка

Пытаясь разработать собственный алгоритм сортировки, я ищу оптимальный эталон, с которым я могу его сравнить. Для несортированного порядка элементов A и отсортированного порядка B , какой эффективный способ вычислить оптимальное количество транспозиций, чтобы добраться от A до B ?

Транспонирование определяется как переключение положения двух элементов в списке, например,

1 2 4 3

имеет одну транспозицию (транспозиция 4 и 3), чтобы сделать его

1 2 3 4

Что-то вроде

1 7 2 5 9 6

требуется 4 транспонирования (7, 2), (7, 6), (6,5), (9, 7)

Обновление (9/7/11): вопрос изменен на использование «транспонирования» вместо «свопов» для обозначения несмежных обменов.

$n$$n-c(\pi)$$c(\pi)$$\pi$$\pi$$\sigma$$A$$B$$n-c(\sigma^{-1}\circ\pi)$

$M(s)$$M_{ij} = 1$$i$$j$$\|M(s) - M(s')\|^2$$d(s,s')$

Обновление: пожалуйста, смотрите комментарии Александра