Come mescolare casualmente un elenco che ha più permutazioni rispetto al periodo del PRNG?

Question

Ho una lista con circa 3900 elementi di cui ho bisogno per produrre permutazioni casuali per produrre una distribuzione statistica. Mi sono guardato intorno e ho trovato questo Maximal Length of List to Shuffle with Python random.shuffle che spiegava che il periodo del PRNG in Python è 2**19937-1, che porta a un elenco con una lunghezza massima di 2080 prima che diventi impossibile generare tutte le possibili permutazioni. Sto producendo solo 300-1000 permutazioni della lista, quindi è improbabile che produca permutazioni duplicate, tuttavia, poiché questo è un metodo per produrre una distribuzione statistica, vorrei avere tutte le possibili permutazioni come potenziali campioni.

Answer 1

Sono d'accordo con @ user2357112 che è improbabile che sia un vero problema - ma sembra che si dovrebbe essere in grado di utilizzare il modulo standard random in modo tale che tutte le permutazioni siano almeno possibili.

Si potrebbe fare un approccio divide et impera. Utilizzare il seed iniziale per suddividere l'elenco in 2 elenchi di circa 2000 ciascuno. Il numero di tali partizioni è circa C(4000,2000) che è approssimativamente 1.66 x 10^1202. Questo è meno che il periodo, il che suggerisce che è almeno possibile che tutte queste partizioni siano generate con random.sample(). Quindi - risemina il generatore di numeri casuali e permuta la prima metà. Quindi - risemina una seconda volta e permute la seconda metà. È possibile che si verifichino ritardi minimi prima delle resezioni in modo da non incorrere in problemi relativi alla risoluzione dell'orologio del sistema. Puoi anche sperimentare partizionando a caso l'elenco iniziale in un numero maggiore di elenchi più piccoli.

Matematicamente, è facile vedere che se si divide in modo casuale una lista in sottoliste in modo che ogni partizione sia ugualmente probabile e quindi si permuta ogni sottolista in modo tale che tutte le permutazioni sublistiche siano ugualmente probabili, e incollare insieme queste sottoliste permutazioni per ottenere una permutazione a lista intera, quindi tutte le permutazioni dell'intera lista sono ugualmente probabili.

Ecco un'implementazione:

import random, time 

def permuted(items, pieces = 2): 
    sublists = [[] for i in range(pieces)] 
    for x in items: 
     sublists[random.randint(0,pieces-1)].append(x) 
    permutedList = [] 
    for i in range(pieces): 
     time.sleep(0.01) 
     random.seed() 
     random.shuffle(sublists[i]) 
     permutedList.extend(sublists[i]) 
    return permutedList 

io non sono sicuro che time.sleep(0.01) è realmente necessario. La mia preoccupazione era che se le reseeds fossero avvenute entro un millesimo di secondo, su alcuni sistemi sarebbe stato possibile utilizzare lo stesso seme.

Come osservazione finale, proprio perché la funzione sopra (con opportuna scelta di pieces) non può essere visualizzata perdere alcuni permutazioni da un argomento semplice conteggio (confrontando il numero di permutazioni con il numero di stati iniziali) questo doesn Di per sé costituisce la prova che tutte le permutazioni sono effettivamente possibili. Ciò richiederebbe un'analisi più dettagliata del generatore di numeri casuali, la funzione di hash che lo semina e l'algoritmo shuffle.

Answer 2

Ci sono PRNG a più lungo termine di MT, ma sono difficili da trovare.

Per ottenere tutti i 3090! combinazioni, hai bisogno di 40.905 bit di entropia. Quello è circa 5kb. Dovresti essere in grado di afferrare un numero di byte che taglia da un posto come random.org molte volte senza problemi. Per ottenere un bilanciamento preciso, dovrai aggiungere alcuni e fare il campionamento del rifiuto. Ad esempio, prendi 12 bit alla volta (0..4095) e rifiuta i numeri più alti dell'indice del ciclo attuale. Ciò potrebbe gonfiare il numero di bit necessari, ma probabilmente non oltre l'8kb.