Permutationen sortieren < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie: Für n [mm] \ge [/mm] 4 kann jede Permutation [mm] \pi \in S_{n} [/mm] mit n-2 Stacks sortiert werden. Dabei sind folgende Operationen erlaubt:
- Die am weitesten rechts stehende Zahl aus der Eingabe kann auf den ersten Stack gelegt werden (Push).
- Für 1 [mm] \le [/mm] i [mm] \le [/mm] n-3 kann das oberste Element aus dem i-ten Stack (Pop) auf den (i+1)-ten gelegt werden (Push).
- Das oberste Element des (n-2)-ten Stacks kann links an das Ausgabewort angehängt werden. |
Meine Lösungsansätze sind folgende:
1. Jedes Permutation [mm] \pi [/mm] hat höchstens n-1 Aufstiege (d.h. [mm] \pi(i) [/mm] < [mm] \pi(i+1).
[/mm]
Jetzt könnte ich folgendermaßen verfahren:
Die Invariante für diese Idee wäre: für alle Stacks gilt: [mm] s_{i} [/mm] < [mm] s_{i+1}, [/mm] wobei [mm] s_{1} [/mm] ganz unten liegt.
Hat [mm] \pi [/mm] n-1 Aufstiege, ist es schon sortiert und kann durch alle Stacks durchgeschoben werden.
Hat [mm] \pi [/mm] weniger als n-1 Aufstiege könnte man sagen:
es wird so lange auf dem i-ten Stack (begonnen bei i=1) gestapelt, bis ein Aufstieg kommt, dann wird mit dem (i+1)-ten Stack begonnen. Das Element n wird direkt in die Ausgabe geschrieben. Dies gibt aber ein Problem, wenn man genau i-2 Aufstiege hat, denn dann hat man genau einen Stack zu wenig und man müsste diesen gesondert behandeln, z.B. durch: sind alle Stacks belegt, ist höchstens noch ein Element < n in der Warteschlange. Laut Konstruktion liegt aber auf jedem Stack nur ein Element und das Element im i-ten Stack > das Element im (i+1)-ten Stack. Man kann also das Element aus einem Stack i<n-2 auf den (i+1) ten Stack schieben, ohne die Invariante zu verletzen und dann das letzte Element < n aus der Warteschlange auf den i-ten Stack legen.
Sind alle Elemente in den Stacks und n in der Ausgabe, dann liegt laut Invariante das Element n-1 immer ganz oben auf einem Stack und kann in die Ausgabe geschrieben werden.
Zweite Idee für n-2 Aufstiege: Hat [mm] \pi [/mm] n-2 Aufstiege [mm] \Rightarrow \pi [/mm] hat 1 Abstieg an der Stelle k mit 0 [mm] \le [/mm] k [mm] \le [/mm] n-1.
[mm] \Rightarrow \forall [/mm] i: [mm] \pi(\pi(k)) [/mm] < i [mm] \le [/mm] n: [mm] \pi(i) [/mm] = i, d.h. man kann alle [mm] \pi(i) [/mm] in diesem Bereich in die Ausgabe schreiben. Danach nutzt man die Tatsache aus, dass man durch 2 Stacks die ursprüngliche Reihenfolge der Elemente wiederherstellen kann, indem man zuerst alle auf den ersten Stack legt (Reihenfolge umgedreht), dann alle auf den źweiten (Reihenfolge wieder original) und anschließend in die Ausgabe schreibt. Genau das macht man mit den restlichen Elementen in der Warteschlange, mit der Ausnahme, dass [mm] \pi(k) [/mm] direkt in die Ausgabe geschrieben wird.
Ich denke, dass beide Ideen die Aufgabe lösen, allerdings sind sie nicht sonderlich elegant, da immer ein Fall extra abgefangen werden muss. Gibt es da noch einen einfacheren Ansatz?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Di 21.10.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
