Poszukuję algorytmu, który będzie porównywał dwie permutacje (czyli ciągi zawierające te same znaki, tyle że ułożone w innej kolejności). Przykładowo mogą to być dwa ciągi KACZKA i AACKKZ.

Kryterium porównania jest liczba mutacji potrzebnych do przekształcenia ciągu 1 w ciąg 2. Przy czym mutacja polega na zamianie dwóch sąsiednich znaków miejscami. Na przykład w ciągu KACZKA po zamianie C i Z otrzymamy KAZCKA. Zamieniane litery muszą zawsze ze sobą sąsiadować z jednym wyjątkiem: pierwszą literę można zamienić miejscami z ostatnią.

Interesuje mnie minimalna liczba takich mutacji potrzebnych do przekształcenia ciągu 1 (np. AACKKZ) w ciąg 2 (np. KACZKA). W przykładzie mamy:

Wejście: AACKKZ, KACZKA
Mutacja 1: AACKZK (Z w lewo)
Mutacja 2: AACZKK (Z w lewo)
Mutacja 3: KACZKA (zamiana pierwszej litery z ostatnią)
Wyjście: 3

Zależy mi też na tym, żeby kod był w miarę optymalny.

Będę wdzięczny za wszelkie uwagi i wskazówki. Próbowałem wykorzystać odległości Hamminga i Levenshteina, ale te algorytmy działają trochę inaczej niż bym chciał.