Two permutations of the integers $1,2,3,…,n$ are given. The first is $p_1=(1,2,…,n)$ and
the second is $p_2 = (i_1,i_2,…,i_n)$ .
(Operation) The following 'operation' can be applied on an arbitrary permutation $(j_1,j_2,…,j_n)$:
Take two adjacent numbers and swap them.
For example, if $n=5$ and one permutation of the numbers $1,2,…,5$ is $p_5=(4,1,5,3,2)$,
then if we apply the 'operation' with this permutation, we can get: $(4,1,5,3,2) -> (4,1,3,5,2)$ – we swapped '$5$' and '$3$' and
received $(4,1,3,5,2)$. Or, for example if we swap '$4$' and '$1$', we will receive $(1,4,5,3,2)$. (End of Operation)
(Transformation Method)
If we try to transform the given permutation $(i_1,i_2,…,i_n)$ in $(1,2,…,n)$ using the given 'operation', we can
do the following: find the number '$1$' in $(i_1,i_2,…,i_n)$ and apply the 'operation' on the number '$1$' until we reach
$pp = (1,-,-,…,-) $, after this find the number '$2$' in $pp$ and apply the operation on '$2$' until we reach $ppp= (1,2,-,…,-)$
and so on for every number from $1$ to $n$.
(End of Transformation Method)
Of course , other ways for transforming $(i_1,i_2,…,i_n)$ into $(1,2,…,n)$ exist , which are different from the suggested method
(Operation above) and these other methods can use a bigger number of 'operation' (a bigger number swaps) in order
to achieve $(1,2,…,n)$.
Question: How can I prove, that the suggested method above for transforming $(i_1,i_2,…,i_n)$ into $(1,2,…,n)$ is doing the minimum number
of 'operation'?
That is – if we transform $(i_1,i_2,…,i_n)$ into $(1,2,…,n)$ using the 'operation' in an arbitrary way then the number of
used 'operation' is $\ge$ than the number of operations used by the described method (Transformation Method above).
Thanks
Best Answer
Define the "wrongness" of a permutation to be the count of how many pairs of elements are out of the desired order relative to each other. Wrongness ranges from 0 when the starting permutation matches the target up to $n\choose 2$ when the starting permutation is a reversal of the target and every pair of elements is out of order.
Note that the swapping operation either increases or decreases the wrongness by exactly 1 (decrease if they were previously out of order, increase if they were previously in order). Thus, the wrongness is a lower bound on the number of swaps required to transform the permutation. Every swap in your "transformation method" decreases wrongness, so it achieves this lower bound.