www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Diskrete Mathematik" - Permutationen sortieren
Permutationen sortieren < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Permutationen sortieren: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 08:46 Fr 17.10.2008
Autor: tut-self

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.

        
Bezug
Permutationen sortieren: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 09:20 Di 21.10.2008
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]