Ich habe eine Liste mit ungefähr 3900 Elementen, die ich brauche, um zufällige Permutationen zu erzeugen, um eine statistische Verteilung zu erzeugen. Ich schaute mich um und fand diese Maximale Länge der zu mischenden Liste mit Python random.shuffle , das erklärte, dass der Zeitraum des PRNG in Python 2**19937-1 ist, was zu einer Liste mit einer maximalen Länge von 2080 führt, bevor es unmöglich wird, alle möglichen Permutationen zu generieren. Ich produziere nur 300-1000 Permutationen der Liste, so dass es unwahrscheinlich ist, dass ich doppelte Permutationen erzeugen werde, da dies jedoch für das Erzeugen einer statistischen Verteilung ist, möchte ich alle möglichen Permutationen als potentielle Muster haben.
Ich stimme mit @ user2357112 überein, dass es unwahrscheinlich ist, dass es ein echtes Problem ist - aber es scheint, als ob Sie in der Lage sein sollten, das Standardmodul random so zu verwenden, dass alle Permutationen zumindest möglich sind.
Du könntest einen Teil-und-herrsche-Ansatz machen. Verwenden Sie den anfänglichen Startwert, um die Liste in zwei Listen mit jeweils etwa 2000 zu teilen. Die Anzahl solcher Partitionen ist ungefähr C(4000,2000) , was ungefähr 1.66 x 10^1202 ist. Dies ist weniger als die Periode, was nahelegt, dass es zumindest möglich ist, dass alle diese Partitionen mit random.sample() erzeugt werden. Dann - resedieren Sie den Zufallszahlengenerator und vertauschen Sie die erste Hälfte. Dann - ein zweites Mal sezieren und die zweite Hälfte vertauschen. Vielleicht werfen Sie vor den Nacharbeiten kleine Zeitverzögerungen ein, damit Sie keine Probleme mit der Auflösung Ihrer Systemuhr haben. Sie könnten auch experimentieren, indem Sie die anfängliche Liste in eine größere Anzahl kleinerer Listen aufteilen.
Mathematisch ist es leicht zu erkennen, dass wenn Sie eine Liste nach dem Zufallsprinzip in Unterlisten partitionieren, so dass jede Partition gleich wahrscheinlich ist, und Sie jede Unterliste so permutieren, dass alle Unterlistenpermutationen gleich wahrscheinlich sind, und diese Unterlistenpermutationen zusammenkleben Um eine Permutation der ganzen Liste zu erhalten, sind alle Permutationen der ganzen Liste gleich wahrscheinlich.
Hier ist eine Implementierung:
%Vor% Ich bin mir nicht sicher, ob time.sleep(0.01) wirklich benötigt wird. Meine Sorge war, dass, wenn die Seeds innerhalb einer Millisekunde stattfanden, auf einigen Systemen der gleiche Seed verwendet werden könnte.
Als letzte Bemerkung, nur weil die obige Funktion (mit geeigneter Wahl von pieces ) nicht gezeigt werden kann, dass bestimmte Permutationen durch ein einfaches Zählargument übersehen werden (Vergleichen der Anzahl von Permutationen mit der Anzahl von Anfangszuständen) stellt an und für sich keinen Beweis dar, dass alle Permutationen tatsächlich möglich sind. Dies würde eine detailliertere Analyse des Zufallszahlengenerators, der Hash-Funktion, die ihn sät, und des Shuffle-Algorithmus erfordern.
Es gibt längere PRNGs als MT, aber sie sind schwer zu finden.
Um alle 3090 zu bekommen! Kombinationen, Sie benötigen 40.905 Bits Entropie. Das sind ungefähr 5kb. Sie sollten in der Lage sein, ein Stück von Bytes dieser Größe von irgendwo wie random.org viele Male ohne Problem zu greifen. Um genau ausbalanciert zu sein, müssen Sie einige hinzufügen und eine Stichprobenentnahme durchführen. Das heißt, nehmen Sie 12 Bits gleichzeitig (0..4095) und weisen Sie Zahlen zurück, die höher sind als Ihr aktueller Schleifenindex. Das könnte die Anzahl der benötigten Bits aufblähen, aber wahrscheinlich nicht über 8kb.