Name dieses Umordnungs- / Sortierproblems?

10

Sie erhalten ein Array der Länge . Jedes Element des Arrays gehört zu einer der Klassen. Sie sollen das Array mit minimaler Anzahl von Swap - Operationen neu zu ordnen , so dass alle Elemente aus der gleichen Klasse immer zusammen gruppiert sind, dass sie ein zusammenhängendes Sub - Array bilden ist. Zum Beispiel: $n$ $K$
Drei weitere gültige Vereinbarungen bleiben bestehen.

\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*}$

Wie heißt dieses Problem in der Literatur? Gibt es einen effizienten Algorithmus dafür?

terminology reference-request sorting arrays Marko Bukal
quelle

1

Ich bin nicht sicher, ob dieses Problem einen Namen hat, obwohl es sicherlich möglich ist. Nicht alle denkbaren Probleme haben Namen.

Yuval Filmus

2

In der Praxis würde dies als Gruppierung bezeichnet . Die Terminologie in der klassischen Algorithmusik ist mir nicht bekannt. (Es ist sicherlich ein interessantes und möglicherweise schwieriges Problem! Das Minimieren der Anzahl von Swaps hat das Gefühl, "die beste Permutation von Gruppen zu finden", was sich wiederum NP-hart anfühlt.)

Raphael

Na Leute, danke fürs Erste. Natürlich bin ich an einer Lösung des Problems interessiert, dachte aber, dass es bereits untersucht wurde, und bat um eine Referenz.

Marko Bukal

6

Hinweis: Es ist ein Härtebeweis, und ich denke, es gibt praktische Algorithmen wie Ganzzahlprogrammierung usw.

Wenn eine BIN_PACKING-Instanz gegeben ist, in der Sie Zahlen in Bins der Größe packen möchten und sichergestellt ist, dass , können wir entwerfen eine Instanz Ihres Problems wie folgt: $K$ $n_1,\ldots,n_K$ $L$ $m_1,\ldots,m_L$ $\sum n_i=\sum m_j=N$

Es gibt Klassen; $K+(N+1)(L-1)$
Die ersten Klassen Größe sind, und jede der übrigen Klassen Größe ;; $K$ $n_1,\ldots,n_K$ $N+1$
Das Array ist in Schlitze der Größe unterteilt: wobei jeder Schlitz der Größe ist mit Klassen gepackt , die zusammenhängend angeordnet sind, und der Rest ist willkürlich angeordnet. $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$

$(N+1)^2$ $N$

Willard Zhan
quelle

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$ tauscht bereits, also können wir nicht) oder "schieben" das Ganze eine Position nach links oder rechts (aber dies bedeutet, dass jeder "

geschoben

N + 1

$N+1$

N + 1

$N+1$

\leq N

$\le N$

1

Ich vermute auch, dass dies NP-schwer ist, aber da keine Idee für einen Beweis vorliegt, sind hier einige schnell berechenbare Untergrenzen aufgeführt, die nützlich sein könnten, um die Optimalität einer heuristischen Lösung zu überprüfen oder eine verzweigte Suche zu beschneiden .

$i$ $n_i$ $i$ $j$ $L_i$ $i$ $j$ $i$ $n_i$ $j$ $L_i$ $i$ $O(n)$ $O(Kn)$

$L_i$ $K=2$ $K$
$L_i$

In Ihrem Beispiel ergeben diese Grenzen beide 1 (0,5 kann im letzteren Fall aufgerundet werden), was natürlich locker ist.

j_random_hacker
quelle

Name dieses Umordnungs- / Sortierproblems?

Antworten: