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.Come mescolare casualmente un elenco che ha più permutazioni rispetto al periodo del PRNG?
risposta
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.
Questa sembra essere un'ottima soluzione. Potresti fornire un esempio di codice per il partizionamento casuale dell'elenco originale? – Darwin
@Darwin Ho aggiunto il codice. –
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.
- 1. Casualmente mescolare un elenco
- 2. Elenco permutazioni
- 3. Come mescolare un elenco in vim?
- 4. Come arrotondare un DateTime al Periodo più vicino
- 5. Dovrei mescolare casualmente prima di inserire nel set STL?
- 6. Stampa elenco di permutazioni binarie
- 7. Come mescolare un ArrayList
- 8. Come posso ottenere le permutazioni di un elenco?
- 9. Caffe ha bisogno di dati da mescolare?
- 10. CFBundleVersion deve essere un elenco separato da un periodo
- 11. Codice Java per permutazioni di un elenco di numeri
- 12. Elenco di adiacenza rispetto al modello di serie nidificato
- 13. Creato casualmente un sottomodulo git
- 14. IonAuth - sembra che mi stia casualmente disconnettendo
- 15. posizione del cursore rispetto al Application
- 16. Testo sottolineato in CSS dove la sottolineatura ha un peso inferiore rispetto al testo?
- 17. Dividere un periodo di tempo in più periodi di tempo
- 18. elastico distribuzione beanstalk più tempo del periodo di timeout, come faccio ad aumentare il periodo di timeout
- 19. Riconoscimento del testo come semplificato rispetto al cinese tradizionale
- 20. Python: come creare un elenco di n numeri e selezionare casualmente un numero qualsiasi?
- 21. indice di ritrovamento di un elemento più vicino al valore in un elenco che non è del tutto allineati
- 22. Come ottenere più risultati di ricerca rispetto al limite del server con Python LDAP?
- 23. NSSet come estrarre l'oggetto casualmente?
- 24. Errore CS1705: "che ha una versione superiore rispetto all'assembly referenziato"
- 25. puntatore al puntatore rispetto a un puntatore
- 26. Qual è il modulo Erlang più performante per archiviare un ampio elenco di valori chiave/termine in un periodo
- 27. Come posso mescolare un intervallo specifico di un ArrayList?
- 28. Verificare se un elenco ha una o più stringhe che corrispondono a un'espressione regolare
- 29. Perché VB ha più parole chiave LINQ rispetto a C#?
- 30. Tabella hash più veloce in C# rispetto al C++?
Si desidera produrre tutte le possibili permutazioni di 3900 elementi? – Tempux
Hai considerato l'utilizzo di 'os.urandom'? urandom è adatto per crypto, quindi penso che dovrebbe funzionare per qualsiasi cosa tu stia facendo. – senshin
Per scopi statistici - in effetti, essenzialmente per qualsiasi scopo - la limitazione delle possibili permutazioni non è un problema.Se sei preoccupato per questo, hai delle deviazioni molto più grandi da una distribuzione ideale di cui preoccuparti. – user2357112