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?
