 |
 |
 |
 |
 |
 |
Startseite » Forum » Zufallspermutationen
Zufallspermutationen
Universität / Fachhochschule
Tags: permutation, Zufall
 
|
  |
|---|
|
Guten Morgen, wie lässt sich eine zufällige Permutation in Laufzeit berechnen? Ich habe zuerst verschiedene Ansätze verfolgt. Die hatten aber wesentlich schlechtere Laufzeiten. Der allernaivste Ansatz wäre : Starte mit einer leeren Liste! Bestimme eine Zufallszahl, die noch nicht in der Liste ist! Füge diese der Liste hinzu! Gehe zu und breche ab, wenn die Liste voll ist! (Für größere wird das allerdings ultra langsam und es kann sogar der Fall auftreten, dass der Algorithmus nicht terminiert, nämlich wenn alle Zufallszahlen schon vergeben sind.) Schließlich habe ich eine Permutation der Länge in Sek. in Python berechnen lassen. Ich glaube, viel schneller geht das nicht. Zumindest nicht in Python :-) Weiß jemand, wie ich das geschafft habe? Tipp : Das Einfügen einer neuen Zahl hat konstante Laufzeit und es müssen keine Elemente gelöscht werden. Ich bin schon gespannt, ob jemand einen schnelleren Algorithmus findet, oder drauf kommt, wie ich das gemacht habe. G Sukomaki EDIT : In C++ läuft die Permutation mit Elementen in bis Millisekunden. Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
import time, random def permrandom(n): p = list(range(1,n+1)) for i in range(n-1,1,-1): j = random.randint(0,i) p[i],p[j] = p[j],p[i] return p if __name__ == '__main__': time_start = time.time() p = permrandom(5000000) time_end = time.time() print(f"running time {time_end-time_start:.3f} s") Leider "zerstört" das Forum hier die notwendigen Python-Einrückungen... Bei mir ergab das eine Laufzeit von ca. 2.3 Sekunden - ist natürlich CPU-abhängig. Der Hauptteil der Zeit dürfte wohl auf die Zufallszahlgenerierung draufgehen. Der Elementaustausch in der Liste ist demgegenüber eher vernachlässigbar. |
 |
|
Das ist interessant : Von der Idee her gehst Du genau so vor wie ich :-) Du kannst, wenn Du einen Array statt einer Liste verwendest noch mal 9% bis 13% Geschwindigkeitsvorteil rausholen. Meine CPU hat einen Takt von 2,6 GHz. Und Deine? > Der Hauptteil der Zeit dürfte wohl auf die Zufallszahlgenerierung draufgehen Das sehe ich genau so. G Sukomaki |
|
|
|
i7-13800H mit bis zu 5.2GHz (Die 14 Kerne dürften bei dem Algorithmus nichts nützen, wenn man nur eine einzige solche Permutation berechnen will, da dann das Vorgehen hier nicht parallelisierbar ist.) Mit array ("L" für 32Bit-Werte) ist es tatsächlich etwas schneller, so ca. 1.9 Sekunden. |
|
|
|
Ich hoffe, Dir hat die Herausforderung Spaß gemacht. Ich erinnere mich daran, dass Du Dich für das Thema "Wahrscheinlichkeit einer fixpunktfreien Permutation" begeistert hast. Zum Nachvollziehen an alle andere : Wir starten mit einer sortierten Liste. Im ersten Schritt wählen wir eine zufällige Zahl und tauschen Sie mit der hintersten Zahl. Natürlich kann die gezogene Zahl auch die größte Zahl sein. Die bleibt dann eben an Ihrem Platz. Im zweiten Schritt wählen wir eine Zahl mit Index bis , also einer weniger als vorher. Die tauschen wir auf den vorletzten Platz. So geht das weiter. Nach dem -ten Schritt gilt : Die letzten Zahlen verbleiben an Ihrer Position, die ersten Zahlen werden weiter durchgewürfelt. So erhalten wir am Schluß eine zufällige Permutation. Bemerkung : Es wäre noch die Korrektheit des Algorithmus zu zeigen. Ich vermute, das läuft auf einen Induktionsbeweis hinaus. Den bekomme ich auf die Schnelle aber nicht hin. Sukomaki |
|
|
|
> Ich erinnere mich daran, dass Du Dich für das Thema "Wahrscheinlichkeit > einer fixpunktfreien Permutation" begeistert hast. Na, die Begeisterung dafür ist 30 Jahre her. Letztens habe ich nur mein Wissen darüber dargelegt. ;-) |
 |
|
Danke für's Mitmachen. Es hat mir Spaß gemacht. Und nebenbei habe ich noch etwas Python gelernt. > if __name__ == '__main__': kannte ich noch nicht. Und das elegante Austauschen zweier Elemente > p[i],p[j] = p[j],p[i] gefällt mir auch gut. Sukomaki |
|
|
|
> Und nebenbei habe ich noch etwas Python gelernt. > if __name__ == '__main__': Ja, dient der Doppelverwendung ein- und desselben Codes mal als Hauptprogramm und dann wieder als Modul (wo man diesen Zweig oben nicht braucht). |
|
|
|
Aha, okay, danke für die Info. Muss ich das verstehen? Ein Modul ist doch etwas, was importiert wird. |
|
|
|
Genau, und als importiertes Modul würde der obige Code nur die Routine "permrandom" importieren, nicht aber den main-Code (und diesen natürlich dann auch nicht ausführen). |
|
|
|
Noch einmal abgehakt. |
1587592
1587441