Generieren Sie eine zufällige Permutation einer großen Liste (in Python).
Ich möchte eine zufällige Permutation der Zahlen erstellen, bei [1,2,...,N]denen Nes sich um eine große Zahl handelt. Ich möchte also nicht alle Elemente der Permutation im Speicher speichern, sondern die Elemente meiner bestimmten Permutation durchlaufen, ohne frühere Werte im Speicher zu behalten.
Irgendeine Idee, wie man das in Python macht?
Eine Möglichkeit ist die Verwendung einer Verschlüsselung. Da die Verschlüsselung reversibel ist, dh eins zu eins, erhalten Sie für einen bestimmten Schlüssel dieselben Nummern zurück, die Sie verschlüsseln, jedoch in einer anderen Reihenfolge.
Sie benötigen eine Blockverschlüsselung mit einer Blockgröße, die groß genug ist, um Ihr maximales N aufzunehmen. Verwenden Sie DES im EZB-Modus für N = 2 ^ 64 - 1. Verwenden Sie AES im EZB-Modus für N = 2 ^ 128 - 1. Auch für andere Größen Verwenden Sie die Hasty Pudding-Chiffre mit variabler Blockgröße oder schreiben Sie Ihre eigene einfache Feistel-Chiffre . Ich gehe davon aus, dass Sie nur ein Shuffle benötigen, kein kryptografisch sicheres Shuffle.
Wenn die Ausgabe größer als N ist, verschlüsseln Sie sie erneut, bis sie kleiner als N ist. Die 1-zu-1-Eigenschaft stellt sicher, dass die Kette großer Zahlen ebenfalls eindeutig ist.
Es ist nicht erforderlich, das gesamte Array im Speicher zu speichern. Jede Nummer kann nach Bedarf verschlüsselt werden. Es werden nur der Schlüssel und der Verschlüsselungsalgorithmus benötigt. Eine leichte Komplikation ist, dass Blockchiffren an [0 ... N-1] arbeiten; Möglicherweise benötigen Sie zusätzlichen Code, um mit den Extremen fertig zu werden.