Alternative zum Hamming-Abstand für Permutationen

Ich habe zwei Saiten, von denen eine eine Permutation der anderen ist. Ich habe mich gefragt, ob es eine Alternative zur Hamming-Distanz gibt, bei der anstelle der Mindestanzahl an erforderlichen Substitutionen die Mindestanzahl an Translokationen ermittelt wird, die erforderlich sind, um von Zeichenfolge a zu Zeichenfolge b zu wechseln .

Meine Zeichenfolgen sind immer gleich groß und ich weiß, dass es keine Fehler / Ersetzungen gibt.

Beispiel:

1 2 3 4 5
3 2 5 4 1

Dies würde mir zwei geben:

3 2 5 4 1 (start)
-> 3 2 1 4 5 
-> -> 1 2 3 4 5

Wenn dies bereits in R implementiert ist, wäre das noch besser.

Das Finden der minimalen Entfernung wird als "Sortieren nach Translokation" bezeichnet. Teil eines Abstracts aus einem Papier :

"Bei zwei signierten multichromosomalen Genomen Pi und Gamma mit demselben Gensatz besteht das Problem der Sortierung nach Translokationen (SBT) darin, eine kürzeste Sequenz von Translokationen zu finden, die Pi in Gamma umwandeln, wobei die Länge der Sequenz als Translokationsentfernung bezeichnet wird zwischen Pi und Gamma. 1996 gab Hannenhalli erstmals die Formel der Translokationsentfernung an, auf deren Grundlage eine $O(n^3)$Algorithmus für SBT wurde angegeben. Im Jahr 2005 haben Anne Bergeron et al. hat dieses Problem erneut aufgegriffen und einen elementaren Beweis für die Formel der Translokationsentfernung gegeben, die zu einer neuen führt$O(n^3)$ Algorithmus für SBT. "

Was hier als "Translokation" bezeichnet wird, wird als Transposition bezeichnet, dh als Permutation von genau zwei Elementen in einer Liste in traditioneller kombinatorischer Sprache.

Wir müssen die minimale Anzahl von Transpositionen finden, die eine Zeichenfolge benötigen $a$ zu einer anderen Zeichenfolge $b$, wo $a, b$sind Permutationen. Es sieht so aus, als würden Sie nach dem Mindestabstand zwischen zwei gegebenen Eckpunkten suchen$a, b \in S_n$ im vollständigen Transpositionsgraphen, der der Cayley-Graph von ist $S_n$ generiert durch die Menge aller Transpositionen.