Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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)$

share|improve this question
    
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

1 Answer 1

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).

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.