Use un número mínimo de intercambios para que cada contenedor contenga bolas del mismo color.

Hay bins, el i ésimo bin contiene un i bolas. Las bolas tienen n colores, hay una i bolas de color i . Sea m = ∑ n i = 1 a i .$n$$i$$a_i$$n$$a_i$$i$$m=\sum_{i=1}^n a_i$

Un intercambio es tomar una pelota de un contenedor e intercambiar con una pelota de otro contenedor. Queremos un número mínimo de intercambios de modo que cada contenedor solo contenga bolas del mismo color.

Sé un caso especial fácil para todo i . (Si a i = 2 para todo i , incluso puede hacerlo intercambiando cada bola como máximo una vez).$a_i\leq 2$$i$$a_i=2$$i$

Editar : Esto está mal porque encontrar es NP-hard.$c(D)$

Si sabemos qué color va a qué contenedor, el problema es fácil.

Considere un dígrafo múltiple , V = { v 1 , ... , v n } . Si sabemos que el color i va a bin b ( i ) , entonces hay k arcos paralelos ( j , b ( i ) ) en A si bin j contiene k bolas de color $D=(V,A)$$V=\{v_1,\ldots,v_n\}$$i$$b(i)$$k$$(j,b(i))$$A$$j$$k$$i$. Cada componente del gráfico es euleriano. El número mínimo de permutas requeridos es , donde c ( D ) es el número de ciclos disjuntos de arco que cubre A . Podemos intercambiar "siguiendo" un circuito euleriano. (un intercambio utilizando un arco de un ciclo mínimo puede cambiarlo a un ciclo mínimo más pequeño y a un bucle automático). Una vez que todo el gráfico está configurado de bucles automáticos, hemos realizado todos los intercambios necesarios.$m-c(D)$$c(D)$$A$

¿Qué tan difícil es este problema en general?

La descomposición máxima de un gráfico dirigido por Eulerian en ciclos disjuntos de borde es NP-Hard, al menos según este libro: Algoritmos y aplicaciones: Ensayos dedicados a Esko Ukkonen en ocasión de su 60 cumpleaños .

Por cierto, aquí hay un artículo que es relevante para el problema que parece estar tratando de resolver: Algoritmo asintóticamente óptimo para el algoritmo de la bandera nacional holandesa .

$n \le 6$