3
$\begingroup$

Let's see the following statement:

Given an array with the first N natural numbers in any order perform at most K(non-negative) swaps in order to obtain the largest possible permutation.

For making the statement more understandable let's say that an array starting with [20, ...] is greater than one starting with [9, ...], so we care only about the value.

Let's consider now the following greedy algorithm for this problem:

While you have swaps try to put the largest numbers in decreasing order from left to right. If a number is already in its position(according to the algorithm) we don't count a swap.

Here an example: [1, 5, 4, 3, 2] with K = 2, answer would be [5, 4, 1, 3, 2].

I was trying to prove this algorithm, but I couldn't find something strong enough. I know that with K swaps we can put at least the largest K number at the beginning, but depending on de input we can have more, and in some cases with one swap we can set 2 numbers at once.

I would appreciate if someone can provide a prove for that algorithm or even another solution for the problem.

Thanks in advance.

$\endgroup$
7
  • 1
    $\begingroup$ I removed the theorem-provers tag, which is for automatic proof checkers. Please make use of the tag summaries when choosing tags. (I'm not surprised that you misunderstood this tag; a striking proportion of the questions tagged with it don't belong there.) $\endgroup$
    – joriki
    Aug 9, 2018 at 5:25
  • $\begingroup$ This is crying out for an inductive proof. $\endgroup$ Aug 9, 2018 at 6:08
  • $\begingroup$ @QthePlatypus Could you please put some light over this? $\endgroup$ Aug 9, 2018 at 6:33
  • $\begingroup$ Just for clarification what is the value of K? $\endgroup$ Aug 9, 2018 at 6:51
  • $\begingroup$ I'm not sure I understand your algorithm, and the example doesn't clear up the important point. Consider this example: $[1, 2, 3, 4, 5]$ with $k=1$. My understanding of your algorithm is that you would try to move the $5$ up, giving $[1,2,3,5,4]$; but this is incorrect. $\endgroup$ Aug 9, 2018 at 8:14

2 Answers 2

1
$\begingroup$

It can be proven that it will take at most K swaps (where K is a natural number $N>K$ inductively.

First consider the situation. $N=1$. The array is the largest possible permutation since it is the only possible permutation.

For the inductive step assume that it takes $K$ swaps to permeate an array of size N ($N>K$) to it's largest form. Consider an array of length $N+1$ if you swap the largest element to the front then at most you have added one swap step, however you now have an array of length N. We know that this will take at most $K$ swaps so it must take at most $K+1$ swaps to do an $N+1$.

By induction the number of swaps done must me at most $K$ swaps where $N>K$.

$\endgroup$
0
$\begingroup$

depending on de input we can have more, and in some cases with one swap we can set 2 numbers at once.
I don't think that would be the case.

I think you understand the main part of why the algorithm works, but are confused by this case.

If you set a higher number to its correct position first, and some another number also gets to its correct position ("by accident") as a consequence of the same swap,
then this case, in fact saves us one swap, because when we will reach the position of that element which was "set accidentally", we don't need to count any swap that time, and we can simply move forward to next position (right).

And also, its not clearly mentioned in your description of the algorithm, so I also clear that -
The swaps you perform during any steps, are also to be reflected in the given array in each step dynamically.

$\endgroup$
7
  • $\begingroup$ I think the order of swaps is also very important, or at least could be potentially $\endgroup$
    – dEmigOd
    Aug 9, 2018 at 6:08
  • $\begingroup$ @dEmigOd yes, the order is important, and we get different answers for different given orders, but this algorithm maximizes the answer that can be produced with limited number of swaps. $\endgroup$ Aug 9, 2018 at 6:10
  • $\begingroup$ @RahulGoswami I'm not confused. The point is I don't know how to prove the algorithm in fact take you to an optimal answer. When you say "by accident" you're talking the same I did, 1 move can put two numbers in its correct position. $\endgroup$ Aug 9, 2018 at 6:23
  • $\begingroup$ @AntonioGonzalezBorrego by saying confused, I meant the part which you needed the answer for. And when 2 numbers are get to their correct positions, you save one swap and skip the number which was "set by accident". $\endgroup$ Aug 9, 2018 at 6:25
  • $\begingroup$ Another point: why would a move need always to put a number(or two) in its correct position? what about a solution where at first we move numbers for positions others than correct, and as a result of this, there would be optimal then to move the numbers, gaining 2 correct positions at once? $\endgroup$ Aug 9, 2018 at 6:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .