Permutations – Minimum Moves to Transform One Permutation into Another

permutations

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 🙂

Best Answer

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.

Related Solutions

[Math] How many combination of numbers

I'll consider the "king" case, without the ability to "pass"; the other cases can be resolved similarly. Let $S_{\text{king}}(n,p)$ be the number of $n$-digit numbers with the king ending at $p \in \{0,1,\ldots,9\}$.

We have:

Boundary conditions: $S_{\text{king}}(1,p)=1$ for all $p \in \{0,1,\ldots,9\}$. (I'll assume we can start wherever we want.)
Recurrence relations:
- $S_{\text{king}}(n,1)=\sum_{p \in \{2,4,5\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,2)=\sum_{p \in \{1,3,4,5,6\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,3)=\sum_{p \in \{2,5,6\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,4)=\sum_{p \in \{1,2,5,7,8\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,5)=\sum_{p \in \{1,2,3,4,6,7,8,9\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,6)=\sum_{p \in \{2,3,5,8,9\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,7)=\sum_{p \in \{0,4,5,8\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,8)=\sum_{p \in \{0,4,5,6,7,9\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,9)=\sum_{p \in \{0,5,6,8\}} S_{\text{king}}(n,p)$,
- $S_{\text{king}}(n,0)=\sum_{p \in \{7,8,9\}} S_{\text{king}}(n,p)$.

This gives:

$$\scriptsize \begin{array}{r|rrrrrrrrrr|r} & p=1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 0 & \text{sum} \\ \hline n=1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 10 \\ 2 & 3 & 5 & 3 & 5 & 8 & 5 & 4 & 6 & 4 & 3 & 46 \\ 3 & 18 & 24 & 18 & 26 & 35 & 26 & 22 & 29 & 22 & 14 & 234 \\ 4 & 85 & 123 & 85 & 128 & 185 & 128 & 104 & 145 & 104 & 73 & 1160 \\ 5 & 436 & 611 & 436 & 642 & 902 & 642 & 531 & 722 & 531 & 353 & 5806 \\ 6 & 2155 & 3058 & 2155 & 3202 & 4551 & 3202 & 2619 & 3601 & 2619 & 1784 & 28946 \\ 7 & 10811 & 15265 & 10811 & 15984 & 22611 & 15984 & 13138 & 17977 & 13138 & 8839 & 144558 \\ 8 & 53860 & 76201 & 53860 & 79802 & 113108 & 79802 & 65411 & 89694 & 65411 & 44253 & 721402 \\ 9 & 269111 & 380432 & 269111 & 398274 & 564041 & 398274 & 326857 & 447787 & 326857 & 220516 & 3601260 \\ 10 & 1342747 & 1898811 & 1342747 & 1988228 & 2816703 & 1988228 & 1630618 & 2234819 & 1630618 & 1101501 & 17975020 \\ \end{array}$$

So there are $17975020$ phone numbers with $10$-digits that can be dialled by a king.

(There are some "sanity checks" we can apply to the above numbers. E.g. $S(n,1)=S(n,3)$ by symmetry.)

The above numbers were computed in GAP using the following code:

M:=[[1,1,1,1,1,1,1,1,1,1]];  # index 10 represents 0
for n in [2..10] do
  M[n]:=[];
  M[n][1]:=Sum([2,4,5],p->M[n-1][p]);
  M[n][2]:=Sum([1,3,4,5,6],p->M[n-1][p]);
  M[n][3]:=Sum([2,5,6],p->M[n-1][p]);
  M[n][4]:=Sum([1,2,5,7,8],p->M[n-1][p]);
  M[n][5]:=Sum([1,2,3,4,6,7,8,9],p->M[n-1][p]);
  M[n][6]:=Sum([2,3,5,8,9],p->M[n-1][p]);
  M[n][7]:=Sum([4,5,8,10],p->M[n-1][p]);
  M[n][8]:=Sum([4,5,6,7,9,10],p->M[n-1][p]);
  M[n][9]:=Sum([5,6,8,10],p->M[n-1][p]);
  M[n][10]:=Sum([7,8,9],p->M[n-1][p]);
od;

In a previous version of the question, there was a condition on the 10-digits being unique. This is a much harder problem, and amounts to counting the number of hamilton paths in various $10$-vertex graphs. Note that finding a hamilton path is an NP-complete problem (ref.). Nevertheless, this enumeration should be achievable using a backtracking algorithm (judging from the above numbers). There's probably not a much better way than this; see these Stackoverflow questions here and here.

[Math] What mathematical algebra explains sequence of circular shifts on rows and columns of a matrix

Permutation theory is all that's needed.

I'll assume that both dimensions of the matrix are at least 2. (If one of the dimensions is $1$, of course only cyclic permutations are possible).

If all the entries are different and both the sides of the matrix have odd lengths, then only even permutations of the elements are possible, because each of the basic moves is an even permutation. (If there are at least one pair of equal elements, then we can always find an even permutation that looks like any odd one, so in that case all rearrangements of the elements are possible).

If at least one of the lengths are even, then every permutation is possible.

In the $2\times 2$ case it is easy to make any desired permutation. The following algorithm works if there are at least 3 columns (and, mutatis mutandis, if there are at least 3 rows):

Put the right elements into position in the two first cells of the first row. Let's call these elements $X$ and $Y$. (This is easy enough because at this step we don't care where any of the other elements go in this phase).
If the permutation we still need to do at this point is odd, then slide the bottom row (if there's an even number of columns) or the last column (if there's an even number of rows) once in your favorite direction. Now the permutation is even.
Express the desired permutation as a sequence of evenly many swaps of elements that are not $X$ or $Y$ (which are already in position). Perform each swap by doing the following three steps:
Let the elements we want to swap be $A$ and $b$. Perform a sequence of moves that place $a$ and $b$ next to each other beneath $X$ and $Y$. Again it it immaterial what happens to element that are not in $\{A,B,X,Y\}$.

Do C2d R2r C2u R1r C2d R2l C2u R1l C2d R2r C2u R2l. This will exchange $a$ and $b$ with the side effect of also exhanging $x$ and $y$, but leaves everything else unchanged:

X Y m m    X q m m    X q m m    X A m m    m X A m    m q A m    m q A m
A B n n -> A Y n n -> n A Y n -> n B Y n -> n B Y n -> n X Y n -> X Y n n
p q . .    p B . .    p B . .    p q . .    p q . .    p B . .    p B . .
p q . .    p q . .    p q . .    p q . .    p q . .    p q . .    p q . .

   m Y A m    Y A m m    Y q m m    Y q m m    Y X m m    Y X m m
-> X B n n -> X B n n -> X A n n -> n X A n -> n B A n -> B A n n
   p q . .    p q . .    p B . .    p B . .    p q . .    p q . .
   p q . .    p q . .    p q . .    p q . .    p q . .    p q . .

Do the opposite of the moves from step (4).

Since steps (4), (5), (6) are repeated an even number of times, their net effect is to leave $x$ and $y$ where they started out. But that means the desired permutation has been achieved.

Best Answer

Related Solutions

[Math] How many combination of numbers

[Math] What mathematical algebra explains sequence of circular shifts on rows and columns of a matrix

Related Question