Während ich einen Kartenmischungsalgorithmus schrieb, realisierte ich, dass es 52 gibt! ~ = 2^225 mögliche Shuffle, die auftreten können. Angesichts dieser Tatsache scheint mir, dass jeder Shuffling-Algorithmus, der auf einem PRNG mit einem Standard-32-Bit- oder 64-Bit-Seed basiert, nur in der Lage wäre, eine Teilmenge aller möglichen Shuffle zu erzeugen. Da meine Plattform nur einen 32 Bit gesetzten PRNG hat (nur die POSIX srandom()/random() Funktionen), habe ich mich gefragt, ob es irgendeinen Weg gibt, dies kreativ zu verwenden, um einen Mischalgorithmus zu erzeugen, der irgendein Ergebnis erzeugen kann. Wenn nicht, kennt jemand einen PRNG-Algorithmus, der in der Lage ist, einen Seed zu verwenden, der aus mehreren 32-Bit-Ganzzahlen besteht, die ich selbst implementieren könnte?Pseudozufallszahlengenerator mit> 64 Bit Seed für eine 52 Karten Deckshuffle
Antwort
Wenn Sie Ihr Problem mit dem aktuellen Zufallszahlengenerator lösen wollen, müssen Sie nur einen Weg finden, den Parameterraum aller möglichen Kartenmischungen in Gruppen aufzuteilen.
Zum Beispiel, wenn Sie einen zufälligen Samen haben, die nur 1 bis 4 sein könnte, aber einen Parameterraum, die 12 mögliche Permutationen hätte, würden Sie mit zwei zufälligen Samen lösen:
(seed1) legen fest, welche Parametergruppe Sie waren in (1-4,5-8 oder 9-12)
(Seed2) definiert, welches Element Ihr Endergebnis ist
(Der Parametersatz muss kein geradzahliges Vielfaches der Seed-Größe für sein Dies zu arbeiten.)
Ich habe diese Methode für sehr große Komplexitätsprobleme in Festkörper Phy verwendet SICS-Modellierung. Dies ist eine rigorose mathematische Lösung, mag jedoch nicht die eleganteste Softwarelösung sein. Viel Glück.
Vielleicht ist eine vollständige Erklärung zu lang, aber ich bin neugierig. Warum funktioniert Ihre Lösung? Wie unterscheidet sich Ihre Lösung von der falschen Lösung, Paare von Zufallszahlen aus demselben Generator zu generieren? Die Verwendung von zwei verschiedenen Samen macht den Generator nicht weniger deterministisch, oder? (Ich erwarte, dass Sie Recht haben, aber ich bin interessiert, warum zu erfahren.) – thb
Nun, in der Physik war der Parameterraum eines Problems leicht in Gruppen aufzuteilen. In Ihrem Fall würden Sie vielleicht jede einzelne Kartenmischungsoption durch Fälle teilen, in denen: Karte 1 nicht permutiert wird, Karte 2 nicht permutiert wird usw. Dann erzeugen Sie eine Zufallszahl, für die keine Karte permutiert wird, und dann eine echte Zufallszahl für welche spezifische Permutation in dieser Gruppe Sie wollen. Ich glaube nicht, dass dies die Zufallsgenerierung mehr oder weniger deterministisch macht. Und ... wenn es so wäre, wäre das wichtig für mich zu lernen. – theJollySin
Also ich denke das ist im Prinzip dann möglich. Ich muss darüber nachdenken, wie dies tatsächlich für die Probleme der Kartenmischung umgesetzt werden könnte. – jjoelson
Interessante Frage. Wenn unter Linux, könnte /dev/urandom oder sogar /dev/random passen. Diese Geräte beruhen auf einem "Entropiepool", der durch das Timing von asynchronen Hardwareereignissen gespeist wird.
jedoch untersuchen auch die mrand48() Familie von Funktionen vorgestellt, in cstdlib oder stdlib.h,, ob nicht auf Linux. Das bringt Ihnen 48 Bit, was näher an dem ist, was Sie wollen.
Viel Glück.
Es gibt viele Zufallszahlengeneratoren mit internen Zuständen> 226 Bit. Wahrscheinlich die beliebtesten sind Mersenne Twister und Marsaglia xorshift +. –