Durata massima dell'elenco da riprodurre con Python random.shuffle?

Question

Ho un lista che mescolo con Python costruito in funzione shuffle (random.shuffle)

Tuttavia, il riferimento stati Python:

Si noti che anche per piuttosto piccola len(x), il numero totale di permutazioni di x è maggiore del periodo di maggior parte dei generatori di numeri casuali; questo implica che la maggior parte delle permutazioni di una lunga sequenza non può mai essere generata.

Ora, mi chiedo cosa significhi questa "len piuttosto piccola (x)". 100, 1000, 10000, ...

Answer 1

TL; DR: si "rompe" sulle liste con oltre 2080 elementi, ma non preoccupatevi troppo :)

risposta completa:

Prima di tutto, si noti che "mischiare" una lista può essere inteso (concettualmente) come generante tutte le possibili permutazioni degli elementi delle liste, e selezionando una di queste permutazioni a caso.

Quindi, è necessario ricordare che tutti i generatori di numeri casuali computerizzati autonomi sono in realtà "pseudo" casuali. Cioè, non sono in realtà casuali, ma si basano su una serie di fattori per cercare di generare un numero che è difficile da indovinare in avanzato, o riprodotto intenzionalmente. Tra questi fattori è in genere il numero generato precedente. Quindi, in pratica, se utilizzi un generatore casuale continuamente un certo numero di volte, alla fine inizierai a ottenere sempre la stessa sequenza (questo è il "periodo" a cui si riferisce la documentazione).

Infine, la docstring su Lib/random.py (il modulo casuale) dice che "Il periodo [del generatore di numeri casuali] è 2**19937-1".

Quindi, dato tutto ciò, se la tua lista è tale che ci sono 2**19937 o più permutazioni, alcune di queste non saranno mai ottenute mescolando l'elenco. Dovresti (di nuovo, concettualmente) generare tutte le permutazioni della lista, quindi generare un numero casuale x e scegliere la xth permutation. La prossima volta, genererai un altro numero casuale y, e scegli la permutazione yth. E così via. Ma dal momento che ci sono più permutazioni rispetto a quelle ottenute con numeri casuali (perché, al massimo dopo i numeri generati da 2**19937-1, inizierai a ottenere di nuovo le stesse), inizierai a selezionare di nuovo le stesse permutazioni.

Quindi, vedete, non è esattamente una questione di quanto è lunga la vostra lista (anche se questo entra nell'equazione). Inoltre, 2**19937-1 è piuttosto una lunga serie. Ma, comunque, a seconda delle tue esigenze di mescolamento, dovresti tenere tutto questo in mente. Su un caso semplice (e con un rapido calcolo), per una lista senza elementi ripetuti, 2081 elementi darebbero 2081! permutazioni, che è più che 2**19937.

Answer 2

Ciò che intendono è che le permutazioni su n oggetti (notate n!) Crescono assurdamente alte molto velocemente.

Fondamentalmente n! = n x n-1 x ... x 1; per esempio, 5! = 5 x 4 x 3 x 2 x 1 = 120 il che significa che ci sono 120 possibili modi per mischiare un elenco di 5 elementi.

Sulla stessa documentazione di pagina Python danno 2^19937-1 come periodo, che è 4.qualcosa × 10^6001 o qualcosa del genere. Basato sulla pagina di Wikipedia su factorials, immagino 2000! dovrebbe essere intorno a questo. (Scusate, non ho trovato la cifra esatta.)

Quindi in pratica ci sono così tante possibili permutazioni che il shuffle prenderà da quello che probabilmente non c'è motivo di preoccuparsi di chi non lo farà.

Ma se è davvero un problema (il cliente fastidioso chiede una garanzia di casualità, forse?), È anche possibile scaricare l'attività a terze parti; vedi http://www.random.org/ per esempio.

Answer 3

ho scritto quel commento nel sorgente Python in origine, quindi forse posso chiarire ;-)

quando il commento è stato introdotto, generatore Wichmann-Hill di Python ha avuto un periodo molto più breve, e non riusciva nemmeno a generare tutte le permutazioni di un mazzo di carte.

Il periodo è astronomicamente grande ora, e 2080 è corretta per la corrente limite superiore. La documentazione potrebbero essere aggiornati con l'avvento di dire di più su questo - ma avevano ottenere terribilmente noioso.

C'è una spiegazione molto semplice: un PRNG del periodo P ha P possibili stati di partenza. Lo stato iniziale determina interamente la permutazione prodotta. Quindi un PRNG del periodo P non può generare più di P permutazioni distinte (e questo è un limite superiore assoluto - potrebbe non essere raggiunto). Ecco perché confrontando N! a P è il calcolo corretto qui. E, in effetti:

>>> math.factorial(2080) > 2**19937 - 1 
False 
>>> math.factorial(2081) > 2**19937 - 1 
True