[Solved]: Use minimum number of swaps so each bin contains balls of the same color

Problem Detail: 

There are $n$ bins, the $i$th bin contain $a_i$ balls. The balls has $n$ colors, there are $a_i$ balls of color $i$. Let $m=\sum_{i=1}^n a_i$.

A swap is take a ball from one bin and swap with a ball from another bin. We want minimum number of swaps such that each bin only contain balls with the same color.

I know a easy special cases $a_i\leq 2$ for all $i$. (If $a_i=2$ for all $i$, then you can even do it by swapping each ball at most once.)

Edit: This is wrong because finding $c(D)$ is NP-hard.

If we know which color goes to which bin, the problem is easy.

Consider a multi-digraph $D=(V,A)$, $V=\{v_1,\ldots,v_n\}$. If we know color $i$ goes to bin $b(i)$, then there are $k$ parallel arcs $(j,b(i))$ in $A$ iff bin $j$ contains $k$ balls of color $i$. Each component of the graph is Eulerian. The minimum number of swaps required is $m-c(D)$, where $c(D)$ is the number of arc disjoint cycles that covers $A$. We can swap by "following" a Eulerian circuit. (a swap using an arc of a minimal cycle can change it to a smaller minimal cycle and a self loop). Once the entire graph is set of self loops, we have made all the necessary swaps.

How hard is this problem in general?

Asked By : Chao Xu

Answered By : Aryabhata

Maximal decomposition of an Eulerian directed graph into edge disjoint cycles is NP-Hard, at least according to this book: Algorithms and Applications: Essays Dedicated to Esko Ukkonen on the Occasion of His 60th Birthday.

btw, here is an article which is relevant to the problem you seem to be trying to solve: Asymptotically optimal algorithm for the Dutch National flag algorithm.

For $n \le 6$, the paper gives a simple algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12560