Użyj minimalnej liczby zamian, aby każdy pojemnik zawierał kulki tego samego koloru

Istnieje kosze The th bin zawierać kulki. Kulki ma kolory istnieją kulki koloru . Niech .i a i n a i i m = ∑ n i = 1 a $n$$i$$a_i$$n$$a_i$$i$$m=\sum_{i=1}^n a_i$

Zamiana polega na wzięciu piłki z jednego kosza i zamianie z piłką z innego kosza. Chcemy minimalnej liczby zamian, tak aby każdy pojemnik zawierał tylko kulki tego samego koloru.

Znam proste przypadki specjalne dla wszystkich . (Jeśli dla wszystkich , możesz to nawet zrobić, zamieniając każdą piłkę najwyżej.)i a i = 2 $a_i\leq 2$$i$$a_i=2$$i$

Edycja : Jest to złe, ponieważ znalezienie jest trudne dla NP.$c(D)$

Jeśli wiemy, który kolor trafia do którego pojemnika, problem jest prosty.

Rozważmy wielocyfrowy znak , . Jeśli wiemy, że kolor idzie do bin , to istnieje równoległych łuków w iff bin zawiera kulek koloru . Każdy element wykresu to Eulerian. Minimalna wymagana liczba zamian to , gdzie jest liczbą cykli rozłącznych łuku, które obejmująV = { v 1 , … , v n } i b ( i ) k ( j , b ( i ) ) A j k i m - c ( D ) c ( D ) $D=(V,A)$$V=\{v_1,\ldots,v_n\}$$i$$b(i)$$k$$(j,b(i))$$A$$j$$k$$i$$m-c(D)$$c(D)$$A$. Możemy zamienić, „podążając” za obwodem Eulera. (zamiana za pomocą łuku minimalnego cyklu może zmienić go na mniejszy minimalny cykl i pętlę własną). Po ustawieniu całego wykresu w pętlach własnych dokonaliśmy wszystkich niezbędnych zamian.

Jak ogólnie trudny jest ten problem?

Maksymalny rozkład grafu kierowanego przez Eulera na cykle rozłączne krawędzi jest NP-trudny, przynajmniej według tej książki: Algorytmy i zastosowania: eseje poświęcone Esko Ukkonenowi z okazji jego 60. urodzin .

btw, tutaj jest artykuł dotyczący problemu, który wydaje się, że próbujesz rozwiązać: algorytm optymalny asymptotycznie dla algorytmu holenderskiej flagi narodowej .

W przypadku , papier podaje prosty algorytm.$n \le 6$