Nazwa tego problemu z przestawieniem / sortowaniem?

10

Otrzymujesz tablicę o długości . Każdy element tablicy należy do jednej z klas. Powinieneś zmienić układ tablicy za pomocą minimalnej liczby operacji wymiany, aby wszystkie elementy z tej samej klasy były zawsze pogrupowane razem, tj. Tworzą ciągłą pod-tablicę. Na przykład: Pozostały trzy inne ważne ustalenia. $n$ $K$

\begin{aligned} [2, 1, 3, 3, 2, 2] ⟶ [2, 2, 2, 1, 3, 3], or \\ [2, 1, 3, 3, 2, 2] ⟶ [1, 2, 2, 2, 3, 3], or \\ [2, 1, 3, 3, 2, 2] ⟶ [3, 3, 2, 2, 2, 1] . \end{aligned}

$\begin{align*} &[2, 1, 3, 3, 2, 2] \longrightarrow [2, 2, 2, 1, 3, 3], \text{ or} \\ &[2, 1, 3, 3, 2, 2] \longrightarrow [1, 2, 2, 2, 3, 3], \text{ or} \\ &[2, 1, 3, 3, 2, 2] \longrightarrow [3, 3, 2, 2, 2, 1]. \end{align*}$

Jak nazywa się ten problem w literaturze? Czy istnieje dla niego wydajny algorytm?

— Marko Bukal
źródło

1

Nie jestem pewien, czy ten problem ma nazwę, choć z pewnością jest możliwy. Nie wszystkie możliwe problemy mają nazwy.

— Yuval Filmus,

2

W praktyce byłoby to nazywane grupowaniem . Nie znam terminologii w klasycznej algorytmii. (Jest to z pewnością interesujący i potencjalnie trudny problem! Minimalizacja liczby zamian ma wrażenie „znajdź najlepszą permutację grup”, co z kolei wydaje się NP-trudne).

— Raphael

Cóż, chłopaki, dziękuję za teraz. Oczywiście jestem zainteresowany rozwiązaniem problemu, ale pomyślałem, że już go zbadałem, więc poprosiłem o referencję.

— Marko Bukal

6

Uwaga: jest to dowód na twardość i myślę, że istnieją praktyczne algorytmy, takie jak programowanie liczb całkowitych itp.

Biorąc pod uwagę instancję BIN_PACKING, w której chcesz spakować liczb do pojemników o rozmiarze , i zapewnione jest, że $K$ $n_1,\ldots,n_K$ $L$ $m_1,\ldots,m_L$ , to możemy zaprojektować przykład problemu w następujący sposób: $\sum n_i=\sum m_j=N$

Istnieją ; $K+(N+1)(L-1)$
Pierwsze klasy mają odpowiednio rozmiar , a każda z pozostałych klas ma rozmiar ;; $K$ $n_1,\ldots,n_K$ $N+1$
Tablica jest podzielona na miejsca o rozmiarze: gdzie każde miejsce o rozmiarze jest wypełnione klasami , ułożonymi sąsiadująco, a pozostałe są dowolnie ułożone. $m_{1}, (N + 1)^{2}, m_{2}, (N + 1)^{2}, m_{3}, \dots, (N + 1)^{2}, m_{L}$ $m_1,(N+1)^2,m_2,(N+1)^2,m_3,\ldots,(N+1)^2,m_L$ $(N+1)^2$ $N+1$

Kluczową obserwacją jest to, że nie ma sensu utrzymywać co najmniej jednej klasy w gnieździe nieporuszonym i przesuwać inne (ponieważ nie zmieni to rozmiaru „kosza”). Tak oryginalne opakowanie bin jest dostępna tylko wtedy, gdy minimalna liczba swapów jest nie większy niż . Ponieważ wiadomo, że BIN-PACKING jest silnie NP-zupełny , twój problem jest NP-trudny. $(N+1)^2$ $N$

— Willard Zhan
źródło

To jest piękne! W przypadku, gdy inni również borykali się z problemami: (1)

zamian jest zawsze wystarczające, aby utworzyć dowolne „pakowanie pojemników”, które chcemy w szczelinach o rozmiarze

, ponieważ wystarczy jedna zamiana, aby przenieść jeden element do ostatecznego lokalizacja bez zakłócania już umieszczonych elementów. (2) Są tylko 2 możliwe rzeczy, które moglibyśmy zrobić z długimi

„strefami buforowymi” pomiędzy „przedziałami”: przesunąć całą klasę długości -

na dowolnym końcu gdzie indziej ( ale to kosztuje

N

$N$

m_{1}, \dots, m_{L}

$m_1, \dots, m_L$

(N + 1)^{2}

$(N+1)^2$

(N + 1)

$(N+1)$

N + 1

$N+1$ zamienia już, więc nie możemy) lub „przesuń” całą rzecz o jedną pozycję w lewo lub w prawo (ale to pociąga za sobą „przesuwanie” każdego ...

— j_random_hacker 10.10.17

... klasa w buforze w lewo lub w prawo jedna pozycja, i choć można to zrobić za pomocą jednego zamiany jednej klasy, istnieje

zajęcia w strefie, więc co najmniej

są potrzebne swapy, więc jeszcze raz: niemożliwy). Ten punkt jest potrzebny do argumentowania, że rozwiązanie problemu PO kosztem

oznacza prawidłowe pakowanie pojemników. (3) Ponieważ pakowanie w bin jest silnie NP-zupełne, zwyczajowe „nie-nie” tworzenia wielu gadżetów (tutaj elementów tablicy) proporcjonalnych do liczb zakodowanych na wejściu nie ma tutaj zastosowania :)

N + 1

$N+1$

N + 1

$N+1$

\leq N

$\le N$

— j_random_hacker

1

Podejrzewam też, że jest to trudne dla NP, ale przy braku pomysłu na dowód, oto kilka szybko obliczalnych dolnych granic, które mogą być przydatne do sprawdzania optymalności rozwiązania heurystycznego lub przycinania wyszukiwania według gałęzi i granic .

Niech klasę zawierać elementy. W każdym prawidłowym rozwiązaniu klasa musi zaczynać się w pewnej pozycji . Możemy zatem obliczyć dolną granicę na koszt „ustalania” klasy , wypróbowując wszystkie możliwe pozycje początkowe , licząc liczbę elementów innych niż w bloku rozpoczynając od pozycji (każda z tych pozycji będzie wymagał zamiany) i biorąc minimum. To można obliczyć dla dowolnego w $i$ $n_i$ $i$ $j$ $L_i$ $i$ $j$ $i$ $n_i$ $j$ $L_i$ $i$ $O(n)$ czas z zastosowaniem przesuwanego okna, dla całkowitego czasu . Dwie ogólne dolne granice to: $O(Kn)$

Weź maksimum we wszystkich . Szczelne dla , prawdopodobnie bardzo słaby dużej . $L_i$ $K=2$ $K$
Zsumuj wszystkie podziel przez 2, zaokrąglając w górę. Jest to ważne, ponieważ każda zamiana może naprawić maksymalnie 2 nieprawidłowe pozycje. $L_i$

W twoim przykładzie obie granice dają 1 (w drugim przypadku 0,5 można zaokrąglić w górę), co oczywiście jest luźne.

— j_random_hacker
źródło