1
$\begingroup$

Problem to get the min. no. of swaps required for arranging pairs togethe.

There exists an array of size 2N with integers ranging from 0 to 2N-1 arranged at random. Each integer is paired with another i.e. 0 paired with 1, 2 paired with 3,...2N-2 paired with 2N-1. What is the minimum number of swaps required to have all pairs next to each other.
E.g. : [5,4,2,6,3,1,0,7] -> [5,4,2,3,0,1,6,7] Output 2 swaps needed

Solution: Greedy Approach

for i from 0 to 2N-2:
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the ith one and swap position with i+1 element

What is the proof for why the above greedy algorithm is optimal?

$\endgroup$
  • $\begingroup$ How do you know that greedy algorithm is optimal? Can you prove a few simple cases such as [1,4,3,6,5,2] and [1,4,3,6,5,8,7,2]? $\endgroup$ – Apass.Jack Dec 24 '18 at 20:49
0
$\begingroup$

The algorithm in the question can be stated more clearly in the following form since considering the odd $i$ does not have any effect once $i-1$ has been take care of.

for even i from 0 to 2N-2:  
    if array[i] and array[i+1] does not constitute a pair:
        find the pair for the i-th one and swap position with i+1 element

Here is an outline of the proof.

Given an array $A$ of size $2N$ with integers ranging from $0$ to $2N-1$, let us construct a graph $G$. Replacing $2i-1$ with $2(i-1)$ for all $i$, we will have a new array $B$ of even integers from $0$ to $2(N-1)$, each of which appears twice. Let $G$ have vertices $0, 2, \cdots, 2(N-2)$.

  • If $B[0]=2i$ and $B[1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
  • If $B[2]=2i$ and $B[3]=2j$, we will add an edge between $2i$ and $2j$ in $G$.
  • $\cdots$
  • If $B[2N-2]=2i$ and $B[2N-1]=2j$, we will add an edge between $2i$ and $2j$ in $G$.

Please note since $2i$ might be the same as $2j$, $G$ may have self-loops. Since each even number appears twice in array $B$, the degree of each of vertices of $G$ is 2 (2-regular graph). That means $G$ is a disjoint union of cycles.

Define a function $s$ from arrays which are permutations of $0, 1, \cdots, 2N-1$ to $\Bbb N$, $s(A)=$ the number of cycles in $G$, where $G$ is obtained from $A$ by the above deterministic construction.

Claim (at most 1 increase with one swap). Suppose an array $A$ is changed to $A'$ by a swap of two elements. Then $s(A')\le s(A)+1$.

Suppose we have proved the claim. Notice that $s(A)=N$, the maximum value of $s$ if and only if all pairs are next to each other. Since you can only increase at most 1 to $s(A)$ by each swap and the greedy algorithm does increase $s(A)$ by 1 with each of its swaps, the greedy algorithm must be optimal.


I will leave the gaps in the above proof as two easy exercises.

Exercise 1: The greedy algorithm increase the value of $s$ by 1 with each of its swaps.

Exercise 2: Prove the claim of at most 1 increase with one swap.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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