Minimum edit distance of two anagrams given two swap operations

Question

Given two anagrams S and P, what is the minimum edit distance from S to P when there are only two operations:

1. swap two adjacent elements
2. swap the first and the last element

If this question is simplified to only having the first operation (i.e. swap two adjacent elements) then this question is "similar to" the classical algorithm question of "the minimum number of swaps for sorting an array of numbers" (solution link is given below)

Sorting a sequence by swapping adjacent elements using minimum swaps

I mean "similar to" because when the two anagrams have all distinct characters:

S:  A B C D
P : B C A D 

Then we can define the ordering in P like this

P: B C A D
   1 2 3 4

Then based on this ordering the string S becomes

S: A B C D
   3 1 2 4

Then we can use the solution given in the link to solve this question.

However, I have two questions:

1. In the simplified question that we can only swap two adjacent elements, how can we get the minimum number of swaps if the anagrams contain duplicate elements. For example,

   S: C D B C D A A

   P: A A C D B C D

2. How to solve the complete question with two swap operations?

Answer 1

One approach is to use http://en.wikipedia.org/wiki/A*_search_algorithm for the search. Your cost function is half of the sum of the shortest distances from each element to the nearest element that could possibly go there. The reason for half is that the absolutely ideal set of swaps will at all points move both elements closer to where they want to go.