5

I have an initial permutation (eg. $\{A,B,C,D,E,F,G,H~\}$) and a final permutation (eg. $\{A,C,F,D,E,G,B,H~\}$) and I want to find how the final permutation can be created from the initial one using minimum number of moves. In my situation a move is removing a character and inserting it to another position.

For example (let the indices of characters start from zero):

$$\{A,B,C,D,E~\} \xrightarrow[\text{B $\rightarrow$ 4}]{} \{A,C,D,E,B~\}$$

It is obvious, that if we wanted to create permutation $\{A,C,D,E,B~\}$ from $\{A,B,C,D,E~\}$, it would be possible to do it also by other moves:

$$\{A,B,C,D,E~\} \xrightarrow[\text{C $\rightarrow$ 1}]{} \{A,C,B,D,E~\} \xrightarrow[\text{D $\rightarrow$ 2}]{} \{A,C,D,B,E~\} \xrightarrow[\text{E $\rightarrow$ 3}]{} \{A,C,D,B,E~\}$$

But I want to find an optimal way (with minimum number of moves). Is there an algorithm to find the moves? Or at least any methods which solve similar problems?

Thank you for help :)

Frédéric
  • 194
Matej Vargovčík
  • 153

1 Answers1

6

Step 1: Find the longest 'increasing' (alphabetized) subsequence.

Step 2: Preserving this subsequence, move the letters not in this subsequence.

Example: Target: DAGFBCE.

Step 1: Longest alphabetized subsequence is ABCE.

Step 2: ABCDEFG to DABCEFG to DAGBCEF to DAGFBCE.

How to carry out step 1: Work from the back of the permutation. The back letter starts an alphabetized sequence of length 1. Put a 1 by the last letter of the sequence. For each previous letter in the permutation, find the letter to its right that it precedes alphabetically and which has the highest assigned number. Add 1 to that value.

In preceding example:

D, A, G, F, B, C, E(1)

D, A, G, F, B, C(2), E(1)

D, A, G, F, B(3), C(2), E(1)

D, A, G, F(1), B(3), C(2), E(1)

D, A, G(1), F(1), B(3), C(2), E(1)

D, A(4), G(1), F(1), B(3), C(2), E(1)

D(2), A(4), G(1), F(1), B(3), C(2), E(1)

Longest sequence is ABCE.

paw88789
  • 40,402
  • 3
    I would also explain why this result is optimal: if $k$ elements of the initial permutation are never moved, they remain in ‘increasing’ order, so the result of these moves must have an ‘increasing’ subsequence of length $k$. If $m$ is the maximal length of an ‘increasing’ subsequence of the desired output, we must therefore move at least $n-m$ elements (where $n$ is the length of the permutation), and it’s clear $n-m$ moves suffice. – Brian M. Scott Jul 17 '16 at 00:37