Transform permutation into another permutation with minimum swaps and/or moves

Question

I have a problem that is a combination of two other asked questions:

• Transform permutation into another permutation with minimum swaps
• Minimum number of moves (not swaps) to transform one permutation into another

That is, given two permutations x and y, what is the minimum sequence of swap and/or move operations to transform x to y?

Definitions:

• swap s(i, j): Swaps the i-th with the j-th element of the permutation.

  Note: this is equivalent to s(j, i).

• move m(i ,j): Removes the i-th element and inserts it to the j-th position. The positions of all elements between i and j are:

  • decremented by one position ("shifted to the left") if i < j
  • incremented by one position ("shifted to the right") if i > j

  Note: this is not equivalent to m(j, i).

• Positions are zero-based.

Example

• x: AFDEBGC
• y: ABCDEFG
• Using only swaps, 5 operations would be needed, for example:

  AFDEBGC => s(1,4) ==
  ABDEFGC => s(4,3) ==
  ABDFEGC => s(3,2) ==
  ABFDEGC => s(2,6) ==
  ABCDEGF => s(6,5) ==
  ABCDEFG
  

• Using only moves, 3 operations would be needed, for example:

  AFDEBGC => m(4,1) ==
  ABFDEGC => m(6,2) ==
  ABCFDEG => m(3,5) ==
  ABCDEFG
  

• Using both swaps and moves, only 2 operations would be needed, for example:

  AFDEBGC => s(1,4) ==
  ABDEFGC => m(6,2) ==
  ABCDEFG