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_ileq 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
