Greedy Algorithm Proof Min Swaps

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?

• 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]? Dec 24 '18 at 20:49

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=2i$$ and $$B=2j$$, we will add an edge between $$2i$$ and $$2j$$ in $$G$$.
• If $$B=2i$$ and $$B=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.