1

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

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
gsakkis
  • 111
  • Note that the first link is to a question about using only adjacent swaps, but you are allowing all swaps. Swaps are also called transpositions, and there are many posts about writing permutations as a product of transpositions, e.g. this one which shows the minimum is $n-s$ where $s$ is the number of disjoint cycles in the permutation. For moves-only I don't know what the optimum is in general, but the worst case is $n-1$ for the reversed list. No idea about combining moves and swaps. – Jaap Scherphuis Oct 24 '22 at 14:57

0 Answers0