Verwenden Sie eine minimale Anzahl von Tauschvorgängen, damit jeder Behälter Bälle der gleichen Farbe enthält

Es gibt - Bins, die i enthält th ist ein i Bälle. Die Bälle haben n Farben, es gibt ein i Bälle der Farbe i . Lassen m = Σ n i = 1 a i .$n$$i$$a_i$$n$$a_i$$i$$m=\sum_{i=1}^n a_i$

Ein Tausch ist, einen Ball aus einem Behälter zu nehmen und mit einem Ball aus einem anderen Behälter zu tauschen. Wir wollen eine minimale Anzahl von Swaps, so dass jeder Behälter nur Bälle mit der gleichen Farbe enthält.

Ich kenne einen einfachen Sonderfall für alle i . (Wenn ein i = 2 für alle i ist , können Sie es sogar tun, indem Sie jeden Ball höchstens einmal tauschen.)$a_i\leq 2$$i$$a_i=2$$i$

Edit : Das ist falsch, weil es NP-schwer ist, .$c(D)$

Wenn wir wissen, welche Farbe in welche Ablage gelangt, ist das Problem einfach.

Man betrachte einen Multi-Digraphen , V = { v 1 , … , v n } . Wenn wir Farbe weiß i geht an bin b ( i ) , dann gibt es k parallele Bögen ( j , b ( i ) ) in A iff bin j enthält k Kugeln der Farbe $D=(V,A)$$V=\{v_1,\ldots,v_n\}$$i$$b(i)$$k$$(j,b(i))$$A$$j$$k$$i$. Jede Komponente des Graphen ist Eulersch. Die Mindestanzahl der erforderlichen Swaps beträgt , wobei c ( D ) die Anzahl der nicht zusammenhängenden Lichtbogenzyklen ist, die A abdecken . Wir können tauschen, indem wir einer Eulerschen Schaltung "folgen". (Ein Tausch unter Verwendung eines Bogens eines minimalen Zyklus kann ihn in einen kleineren minimalen Zyklus und eine Selbstschleife ändern.) Sobald der gesamte Graph aus Self-Loops besteht, haben wir alle notwendigen Swaps durchgeführt.$m-c(D)$$c(D)$$A$

Wie schwer ist dieses Problem im Allgemeinen?

Die maximale Zerlegung eines Euler'schen gerichteten Graphen in kantendisjunkte Zyklen ist NP-schwer, zumindest gemäß diesem Buch: Algorithmen und Anwendungen: Essays, die Esko Ukkonen anlässlich seines 60. Geburtstages gewidmet sind .

Übrigens, hier ist ein Artikel, der für das Problem relevant ist, das Sie zu lösen scheinen: Asymptotisch optimaler Algorithmus für den niederländischen Nationalflaggenalgorithmus .

$n \le 6$