Hallo,
vorweg: Ich suche nur nach einem zuverlässigen Algorithmus.
Hier mal die Aufgabenstellung (vereinfacht):
Input:
Ein 2-dimesionales Array mit Zahlenwerten, z.B.
1360 2610 2610 2610
1360 2610 2610 1360 1360
Verarbeitung/Ziel:
die Zahlen so sortieren, dass insgesamt möglichst wenige Wechsel entstehen. „Insgesamt“ heißt, dass die vorhergehende und die nachfolgende Zeilen mitberücksichtigt werden sollen, also beim Zeilenwechsel möglichst kein Wechsel des Wertes auftritt. Die Werte können dabei nur innerhalb einer Zeile verschoben werden.
Die Abarbeitung erfolgt von links nach rechts und von oben nach unten (also so wie man es hier in Textform liest).
Output:
Das sortierte 2-dimesionale Array mit Zahlenwerten, z.B.
1360 2610 2610 2610
2610 2610 1360 1360 1360
-> Die Anzahl der "Wertewechsel" wurde von 4 auf 2 reduziert
Ich habe hier mal ein Beispiel mit echten Daten (zur Vereinfachung als Buchstaben) eines möglichen Inputs (pro Zeile können theoretisch ca. 10 verschiedene Werte stehen)
aabb
bbaa
cddd
eeec
eeef
eeef
eeef
eeef
eeef
eeef
gghe
iiig
Dann bin ich mal hingegangen und habe das Vorkommen eines jeden Buchstaben in ein Array gepackt, das sähe dann so aus
Grafik Array_Vorkommen.png
Mit folgendem Algorithmus könnte man dann dieses neue Array abarbeiten:
1. Es werden nur die Felder mit "1" betrachtet
2. In einer Spalte kann man "springen", jedes Feld darf aber nur ein Mal "besucht" werden.
3. Wenn alle Felder einer Spalte besucht wurden, muss man nach rechts in die nächste Spalte. -> Dabei nach Möglichkeit nicht die Zeile wechseln.
Darstellung, in welcher Reihenfolger die Felder abgearbeitet werden sollten:
Grafik Array_Reihenfolge.png
Nach diesen Regeln würde man z.B. folgenden Output generieren (pro Spalte hier eine Zeile):
ab
ba
dc
ce
ef
fe
ef
fe
ef
fe
ehg
gi
was dann auf folgendes erweitert werden könnte und gleichzeitig das optimal sortierte Array wäre
aabb
bbaa
dddc
ceee
eeef
feee
eeef
feee
eeef
feee
ehgg
giii
Ich hoffe ich konnte die Aufgabenstellung anhand dieses Beispiel gut genug erklären.
Kennt ihr dafür einen Algorithmus?
Ist mein Ansatz über das Array "Vorkommen eines Wertes" ein richtiger Ansatz? Gibt es einen Algorithmus, um in diesem Array einen "Pfad" nach den oben beschriebenen Regeln (besonders Regel 3) zu finden?
Das Problem bei beiden Ansätzen dürfte ja sein, dass man ggf. zurückspringen und die bisherige Sortierung komplett über den Haufen werfen muss, um die optimale Sortierung zu erzielen.