3

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

Community
  • 1
citroen
  • 31
  • Firstly I'll assume you're operating only on a finite subset of the integers. Which algorithm is the fastest will depend heavily upon the starting position of the integers. So for the question to be meaningful a common sense assumption is to say all orderings of $n$ integers are equally likely and to choose the method with the least total steps to solve every different possible enumeration. I suspect your method is not the most efficient since it will only move number short distances, so it could be inefficient at moving them from one end to the other. – it's a hire car baby Aug 19 '16 at 17:58
  • Yes, only finite subsets of integers. Also, i disagree with the second sentence:"Which algorithm is the fastest will depend heavily upon the starting position of the integers" . The suggested method is doing the minimum number of swaps no matter what is the given permutation p2 = (i1,i2,...,in).The purpose is to be given proof that it is true. I know it is true, bu i can't proove it. – citroen Aug 19 '16 at 18:06
  • Maybe I misunderstand the question but I'm thinking if your arbitrary permutation happens to be all numbers in their original places except the $n$ and $(n-1)^{th}$ digits are interchanged then this will be solved less slowly by an algorithm that begins by interchanging the first 2 than a permutation in which the $1^{st}$ and $2^{nd}$ digits are interchanged. – it's a hire car baby Aug 19 '16 at 18:10
  • It is possible I misunderstand the algorithm you're proposing. – it's a hire car baby Aug 19 '16 at 18:11
  • Also, just to give some simple hint(although good math competitor will notice this quickly) - nobody claims, that the method, enclosed in #### in my post is the ONLY method that is doing the transformation from arbitrary permutation (i1,i2,...,in) ti (1,2,...,n) with minimum number of swaps. For example, if we try to work firstly with the number 'n' and move it to the right end, then move the number 'n-1' to the right , and so on, we will also receive the (1,2,...,n) - this is just reversed order of the method enclosed in #### in my first post and this will have the same number of swaps. – citroen Aug 19 '16 at 18:13
  • Well, you say if p2=(1,2,3,4,5,.....,n-3,n-2,N,N-1) , right? Everything is ok with the method enclosed in ####. It will leave every number at its original position, because no need to swap anything except 'n-1' and 'n'. It will chek for '1' and will see it is on its place.Then will go for '2' - it is also on its place, then go for '3', and so on until it reach 'n-1' and it will swap 'n-1' with its adjacent ,which is 'n'(and not with 'n-2' ). I think its ok – citroen Aug 19 '16 at 18:18
  • Hint: A method which begins by switching the right hand two numbers and then stops will be the fastest method with no exceptions, for the string I described. – it's a hire car baby Aug 19 '16 at 18:32
  • @RobertFrost - That is exactly what the proposed algorithm does for the string you described. The "speed" of the method is measured by the number of switches it performs. If it doesn't need to move an element, that doesn't increase the number of switches, regardless of how long it takes to determine that the element is in the right position. – Shagnik Aug 20 '16 at 06:28

1 Answers1

2

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.

Mike H
  • 21
  • 2