abgebrochenes Bubble-Sort |
| 30.05.2008, 23:30 | Ruebi | Auf diesen Beitrag antworten » | ||||
| abgebrochenes Bubble-Sort Gegeben sind alle 13 Spielkarten einer konstanten Farbe (also: Ass, 2 bis 10, Bube, Dame, König - meinetwegen in Pik). Diese sind in beliebiger Reihenfolge geordnet. Nun läuft von links nach rechts ein Bubble-Sort-Algorithmus, der von klein nach groß sortieren soll. (Also: zwei benachbarte Karten werden verglichen, zur Not getauscht, dann kommt das nächste Pärchen). Nun wird das Bubble-Sort aber aufgrund eines Computerfehlers nicht bis zum Ende durchgeführt und bricht nach einer positiv ganzzahligen Anzahl von Durchgängen n ab. (n<13) Mit welcher Wahrscheinlichkeit sind die 13 Karten nach n Durchgängen richtig sortiert? |
||||||
| 30.05.2008, 23:33 | Ruebi | Auf diesen Beitrag antworten » | ||||
Also, ich würde vorschlagen, hier über die direkte Wahrscheinlichkeitsdefinition zu gehen: P=(Anzahl der günstigen Ereignisse)/(Anzahl der möglichen Ereignisse) Der Nenner ist klar, denn es gibt 13! mögliche Ausgangsstellungen, aber wie bestimme ich den Zähler? Also, wie kann man die Anzahl der günstigen Ausgangsstellungen in Abhängigkeit von n bestimmen? Ich hoffe, ihr könnt mir helfen! |
||||||
| 30.05.2008, 23:45 | Ruebi | Auf diesen Beitrag antworten » | ||||
Wenn das für ein allgemeines n zu schwierig ist - mir würde es ja auch schon helfen, das mal an einem Spezialfalls aufgezeigt zu bekommen, meinetwegen 3 oder 4 Durchgänge. Vielleicht finde ich den Rest dann allein. Ihr sollt mir ja nicht alles lösen, sondern nur mal Anhaltspunkte geben, also vielleicht einen Spezialfall betrachten. |
||||||
| 31.05.2008, 08:18 | AD | Auf diesen Beitrag antworten » | ||||
Ein interessantes Problem, kann mich auch nicht erinnern, das schon mal irgendwo gesehen zu haben. Hmm, mir fällt auf Anhieb auch nicht die zündende Idee ein, kann aber zumindest folgende Anregung beisteuern: In einem Durchgang kann zwar eine Karte sehr weit nach rechts wandern, aber nur maximal eine Position nach links. D.h. wenn man zu einer gegebenen Permutation für jede Karte die Anzahl "nötigen" Schritte nach links zählt (sofern es für die Karte überhaupt nach links gehen muss) und dann das Maximum dieser Schrittanzahlen über alle betroffenen Karten der Permutation bildet, dann ist diese Zahl eine untere Schranke für die Anzahl der nötigen Bubblesort-Durchläufe bis zur vollständigen Ordnung. Könnte sogar sein, dass das nicht nur eine Schranke, sondern sogar die genaue Anzahl ist - aber so gründlich hab ich das am frühen Morgen noch nicht durchdacht. 
Vielleicht hilft dir das weiter - obwohl natürlich die Anzahl der Permutationen mit diesem Kriterium auch nicht gerade einfach zu zählen sein wird. Beispiel: (ich nehm mal eine Permutation von 1 - 13 statt der Karten) 7 , 4 , 3 , 12 , 8 , 9 , 2 , 5 , 1 , 13 , 10 , 11 , 6 Dann ergeben sich die o.g. "nötigen" Schrittzahlen gemäß Also ist 8 das Maximum dieser Schrittzahlen - und wenn ich mich nicht verrechnet habe, auch die Anzahl der nötigen Bubblesort-Durchläufe. |
||||||
| 31.05.2008, 10:41 | Ruebi | Auf diesen Beitrag antworten » | ||||
Erstmal danke für deinen Ansatz. In der Tat ist das ein kniffliges Problem, aber es sind ja nicht die maximal benötigten Durchläufe gefragt, sondern die Wahrscheinlichkeit, dass die Reihe danach geordnet ist bei festem n, meinetwegen n=3. Demzufolge: Aus wievielen Ausgangsstellungen der 13 Karten kann man mit 3 Bubble-Sort-Läufen eine geordnete Reihe herstellen? Mir ist schon klar, dass z.B. die niedrigste Karte (das Ass) schlimmstenfalls auf Position 4 sein darf, sonst klappt das nicht....aber das ist ja auch noch nicht die Lösung. |
||||||
| 31.05.2008, 10:57 | AD | Auf diesen Beitrag antworten » | ||||
Genau dem sollte doch meine Anregung (!) dienen:
Habe ja gar nicht behauptet, dass das die Komplettlösung ist. Du musst sie ja nicht annehmen... |
||||||
| Anzeige | ||||||
|
|
||||||
| 31.05.2008, 11:05 | Ruebi | Auf diesen Beitrag antworten » | ||||
Hmm, so war das garnicht gemeint, dass ich hier eine Komplettlösung möchte, das war eher zu mir "selbst" gesprochen. Betrachte es als inneren Monolog^^. Fällt dir oder jemand anderem ein "systematisches Vorgehen" ein, was man nutzen kann? Und was bedeuten pi und s in deiner Tabelle genau? |
||||||
| 01.06.2008, 15:32 | Ruebi | Auf diesen Beitrag antworten » | ||||
So, jetzt habe ich deine Tabelle verstanden. Ich stimme dir zu, dass z.B. die 1 nur maximal an der 4. Position stehen darf, wenn wir mal 3 Durchläufe annehmen. Aber das lässt sich ja nicht so leicht auf alle Karten übertragen. Gibt es vielleicht noch einen systematischen Ansatz über irgendwelche Formeln, denn mit Auszählen wird das speziell dann für ein unbestimmtes n sehr schwer. Vielleicht fällt euch ja noch etwas ein, ich stehe auf ziemlich verlorenem Fuß. Schon einmal danke im Voraus für alle folgenden Antworten. |
||||||
| 01.06.2008, 19:01 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||
RE: abgebrochenes Bubble-Sort
Nach meinem belieben, dann sortier ich sie doch gleich richtig, dann ist die wahrscheinlichkeit auch leicht zu berechnen 
Oder soll das heissen, daß die Verteilung über alle Permutationen gleichverteilt ist? |
||||||
| 01.06.2008, 20:06 | Ruebi | Auf diesen Beitrag antworten » | ||||
Es heißt, dass zu Beginn jede der 13! möglichen Konstellationen vorliegen kann. Und es ist gefragt, wieviele dieser Konstellationen man in eine geordnete Reihe überführen kann mit meinetwegen 3 Durchgängen (allgemein: n Durchgänge). |
||||||
| 01.06.2008, 20:48 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||
Es ist schon wichtig, ob jede der 13! möglichen Kombinationen gleich wahrscehinlich vorkommt. Du mußt meine Penibilität entschuldigen, aber bei Stochastik bin ich vorsichtig geworden, man kann sonst jeden Wert rauskriegen, wenn man die Grundannahmen leicht verschiebt. Zum Thema: Ich denke der maximale entfernung die eine Karte zu weiter rechts liegt ist die genaue anzahl der nötigen Schritte. Liegt eine Karte die an Stelle n gehört an einer Stelle n+i (also zu weit rechts), dann macht sie in dem Durchlauf genau einen Schritt nach links. Schliesslich ist links von ihr mindestens eine Karte die höher ist als sie selbst und sich an ihr vorbeibubblen wird. Gruß, Proto |
||||||
| 01.06.2008, 21:11 | AD | Auf diesen Beitrag antworten » | ||||
Naja, es besteht wohl von Anfang an Konsens, dass wir hier den Laplaceraum der Permutationen betrachten, d.h. alle gleichwahrscheinlich.
Der Meinung bin ich mittlerweile auch, obwohl ich es hieb- und stichfest nicht mit zwei, drei Sätzen erklären kann. Allerdings scheint es wirklich verflucht schwierig zu sein, die zugehörige Anzahl Permutationen zu fester maximaler Entfernung zu zählen. Mir ist zumindest nichts geeignetes bisher eingefallen. 
|
||||||
| 01.06.2008, 23:02 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||
Jede Karte die zu weit rechts liegt rückt jede Runde genau einen Stelle nach links. Wenn keine Karte mehr zu weit rechts liegt, dann liegt auch keine mehr zu weit links. Wenn wir ausschliessen können das die Karten zurück nach rechts wandern, dann sollte das als Beweis doch eigentlich reichen. PS: Was den stochastischen/kombinatorischen Kram des Lösung betrifft lehn ich mich zurück und überlass das den Mathematikern
|
||||||
| 01.06.2008, 23:07 | Ruebi | Auf diesen Beitrag antworten » | ||||
Hallo ihr zwei, ich muss euch in der Hinsicht zustimmen: Alle 13! Anfangsmöglichkeiten sind gleichwahrscheinlich. Und auch die Tatsache, dass sich eine Karte, die zu weit rechts liegt pro Durchlauf nur um maximal einen Schritt nach links bewegen kann, ist einleuchtend. Das würde zumindest schonmal einige Möglichkeiten ausschließen lassen. -das Ass darf nicht weiter als an Stelle 4 liegen -die 2 darf nicht hinter Stelle 5 liegen -die 3 nicht hinter Stelle 6 usw. Damit ließen sich zumindest schonmal gesondert ein paar Möglichkeiten ausschließen, nur gibt es ja auch Fälle, in denen mehrere Merkmale gleichzeitig vorliegen, das ist kompliziert daran. ...und eben wäre es günstig, wenn man eine Formel fände, mit der man das besser bestimmen kann, als mit Auszählen, aber die scheint recht knifflig. |
||||||
| 01.06.2008, 23:15 | AD | Auf diesen Beitrag antworten » | ||||
Nicht drücken! Womöglich ist dem Problem sowieso nur rekursiv beizukommen - und da wäre es schon wichtig, ob nun P oder NP oder wie auch immer die Informatiker das bezeichnen...
|
||||||
| 02.06.2008, 01:33 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||
Nagut, dann versuch ich es mal mit etwas was polynomieller Laufzeit gut ausrechenbar ist: Will man von rechts anfangend eine gültige Kombination legen, also eine in der keine Karte mehr als n Plätze zu weit rechts liegt, dann hat man die ersten Runde genau (n+1) Möglichkeiten. Entweder die richtige Karte (das As), oder eine die 1 bis n Plätze abweicht. Für die nächsten Stellen gilt: Die Karten die bisher gelegt werden durften, dürfen auch wieder gelegt werden, schliesslich waren sie ja vorher auch nicht zu weit rechts. Zusätzlich gibt es eine neue Karte die jetzt nicht mehr zu weit rechts ist. Dafür muß man wieder eine abziehen, nämlich die die schon gelegt wurde. Also gibt es für die nächsten Stellen immer (n+1) mögliche Karten. Das geht solange bis man an der n-ten Stelle ist, dann ist alles erlaubt was da ist. Also sind für die Plätze 13 bis n+1: es sind (n+1) Karten möglich. Und für die Plätze i aus n bis 1: Es sind i Karten möglich. Das ergibt zusammen Möglichkeiten. Gruß, ProtoX |
||||||
| 02.06.2008, 10:42 | Ruebi | Auf diesen Beitrag antworten » | ||||
Hallo Protox, ich verstehe deine Ausführungen leider nicht ganz. Den Anfang kann ich gut nachvollziehen, du sagst, dass die letzte Karte entweder die größte sein muss oder eine, die maximal n Plätze zu weit rechts liegt >> n+1 Möglichkeiten Aber könntest du den nachfolgenden Absatz noch einmal etwas genauer erklären, meinetwegen auch für einen Spezialfall wie n=3 (das macht es im Allgemeinen leichter verständlich). Wenn ich dich richtig deute, heißt das, dass auf der vorletzten Stelle dann alle Karten liegen dürfen, die vorher auf der 13. Stelle schon hätten gelegt werden dürfen. Eine dieser Möglichkeiten ist aber bereits gelegt (nämlich die 13. Karte), aber es kommt eine weitere hinzu (die Position 13-(n+1)), da man ja eine Stelle vorgerückt ist. >> n+1 Möglichkeiten. So kann man weiter machen bis zur n-ten Stelle, denn da kann dann alles liegen, was noch übrig ist (Schließlich kann man es dann in maximal n Zügen an die erste Stelle bringen oder aber ganz nach hinten, da hinten gewiss noch kleinere Zahlen sein müssen). Was genau bezeichnet das i, das du für die Plätze n bis 1 als Anzahl der Kartenmöglichkeiten angegeben hast? Und wie kommst du auf deine Gleichung? Ich verstehe den zweiten Faktor, schließlich gibt es ja für 13-n Karten n+1 Kartenmöglichkeiten, aber wie kommt das n! da noch rein? Vielen Dank. |
||||||
| 02.06.2008, 10:59 | AD | Auf diesen Beitrag antworten » | ||||
@PrototypeX29A Ja, sieht gut aus. Hätte die Sache auch mal schrittweise von rechts betrachten sollen, war ja gar nicht so schwer.
Wenn also die Anzahl der nötigen Bubblesort-Durchläufe bis zur vollständigen Ordnung bei insgesamt Karten ist, dann hast du die Verteilungsfunktion für aufgestellt. @Ruebi Dir ist doch alles klar, von der letzten 13.Stelle rechts rückwärts gehend bis zur (n+1)-ten Stelle. Und an die restlichen n Zahlen müssen nun keine Bedingungen mehr gestellt werden: Egal, welche Zahlen da stehen - sie sind entweder links der Zielposition oder maximal n-1 Positionen zu weit rechts, also im Rahmen dessen, was man mit n Durchläufen packen kann. Also ist jede Anordnungsmöglichkeit dieser n Restkarten auf den äußeren linken n Positionen zulässig, und das sind nun mal Möglichkeiten. |
||||||
| 02.06.2008, 11:10 | Ruebi | Auf diesen Beitrag antworten » | ||||
Okay, dankeschön, ihr habt mir echt geholfen. Vielen Dank nochmals. Jetzt, wo man die Lösung sieht, da muss man sagen, dass es doch noch relativ human war, aber darauf zu kommen, das ganze von rechts aufzuziehen, das war wohl der Kniff. Meine Fragen sind damit erledigt, ich bedanke mich. Beste Grüße. |
||||||
| 02.06.2008, 16:41 | PrototypeX29A | Auf diesen Beitrag antworten » | ||||
Die ersten Lösungsansatze waren auch über links, oder eine Induktion über die Größe der Permutation, zum Glück war ich dazu zu faul. |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
