Greedy Algorithm Proof Min Swaps

Question

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]?

Answer 1

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 2ドルN$ with integers ranging from 0ドル$ to 2ドルN-1$, let us construct a graph $G$. Replacing 2ドルi-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 2ドルi$ and 2ドルj$ in $G$.
• If $B[2]=2i$ and $B[3]=2j$, we will add an edge between 2ドルi$ and 2ドルj$ in $G$.
• $\cdots$
• If $B[2N-2]=2i$ and $B[2N-1]=2j$, we will add an edge between 2ドルi$ and 2ドルj$ in $G$.

Please note since 2ドルi$ might be the same as 2ドルj$, $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.