# Minimum number of moves to convert a list of any integers into a permutation

Given a list of integers of size n, how to find the minimum number of moves to convert it to a Permutation?

In one move, we are allowed to decrease or increase any element of the list by one.

For example, $n = 3$ and the list being $(-1, -1, 2)$. The minimum number of moves required is $6$ to convert it to the permutation $(1,3,2)$

-
Hi, welcome to Math Stack Exchange. Could you please clarify your question -- what exactly is the transformation from $\{-1,-1,2\}$ to $\{1,3,2\}$? – gt6989b Mar 21 '13 at 16:00
You mean perhaps adding (or subtracting) ones to each element? (Warning: you should avoid the use of braces for your list, as braces usually denote sets.) – Andreas Caranti Mar 21 '13 at 16:04
@ Andreas: Yes that's exactly what I meant to. (Thanks for the warning, I have edited). – Nishi Mar 21 '13 at 16:11

Hint:: If I understand your question correctly -
If your list is $( a_1, a_2, \ldots a_n )$, and your permutation $\sigma$ must be a permutation of $( 1, 2, \ldots, n )$, then the minimum number of moves to go from list to $\sigma$ is

$$\sum_i | a_i - \sigma(i) |$$

Hence, we are looking for the minimum possible value of this summation, over all possible permutations.

Hint: The minimum occurs when the order of the elements $\sigma^*(i)$ is the exact same as the order of the elements $a_i$. (Note that this is not the only possible equality case.)

You can proof this using the triangle inequality, and consider what happens when you swap $\sigma(i), \sigma(j)$ (i.e. a smoothing argument).

-
Yes, you do get the problem correctly. But I am not getting your hint. What exactly does it mean when you say "he minimum occurs when the order of $\sigma^*(i)$ is the exact same as the order of $a_i$." (I am not a mathematician, Please pardon my ignorance) – Nishi Mar 21 '13 at 16:18
i.e. if you look at the list $(-1, -2, 2)$, you should aim to transform it into $(2, 1, 3)$. The order of the elements in both sets is that the second term is the smallest, then the first, and finally the last term is the largest. In cases of ties like $(-1, -1, 2)$, it doesn't matter whether you use $(1, 2, 3)$ or $(2, 1, 3)$. – Calvin Lin Mar 21 '13 at 16:24
It means we might as well suppose $a_i$ is sorted to begin with. – muzzlator Mar 21 '13 at 16:25
@muzzlator Precisely. The "makes sense" provides some justification. However, you still need to show that it is the minimum possible. For example, Nishi gave the case that $(-1, -1, 2)$ to $(1, 3, 2)$ takes 6 steps, which is the same as taking it to $(1, 2, 3)$. There is a slight trick involved, which has to do with the absolute value sign. – Calvin Lin Mar 21 '13 at 16:28