Tutti i numeri pseudo generati casualmente in un determinato periodo sono univoci?

Come dice correttamente la risposta accettata, sarebbe un orribile PRNG. Vuoi che il periodo del generatore sia di molti ordini di grandezza maggiore del numero di valori che genera; la tua proposta è che siano uguali.

Ma la tua domanda non era "critica questa idea", ma piuttosto

does a practical, usable pseudo-random number generating algorithms exist that never repeat the same number twice until their period is up.

Certo, è facile. Eccone uno:

• Scegli il periodo che desideri. Chiamalo p .
• Chiaramente il numero di valori generati dal PRNG non deve essere inferiore a p , perché altrimenti, secondo il principio del pigeonhole, si ripete un'uscita in meno di p passi. Supponiamo che il numero di possibili valori generati dal PRNG sia anche p , e che generi numeri da 0 a p-1 .
• Ora il nostro algoritmo è semplice. Abbiamo due semi, che chiamiamo s e i , entrambi tra 0 e p-1 . s può essere qualsiasi cosa. i deve essere qualsiasi numero coprime a p . L'ennesimo elemento generato dal PRNG con i semi s e i è (n * i + s) % p . Ovvero, moltiplica i per n , aggiungi s e prendi il resto quando quel valore è diviso per p .
• Questo ti dà una sequenza di numeri pseudo-casuali incredibilmente crappy che si ripetono con p periodo e non generano mai lo stesso numero nel periodo, e ogni numero è compreso tra 0 e p-1 . Godetevi.
• Facciamo un esempio. p=10 , i=3 , s=5 , la sequenza è 5, 8, 1, 4, 7, 0, 3, 6, 9, 2 e poi si ripete.
• Si noti che il bit basso della sequenza prodotta da questo algoritmo alterna ogni fase successiva; è davvero pessimo!
• Hai chiesto se esiste un algoritmo, non esiste alcun algoritmo buono .

Questo è stato davvero schifoso. Possiamo fare di meglio?

Fondamentalmente quello che stai chiedendo è "Ho bisogno di una permutazione casuale di questo set". Ci sono molti buoni algoritmi per questo. Poiché esistono% permutazioni di% co_de di un insieme con% elementi esclusivi dip!, ciò che devi fare è scegliere un numero uniforme tra 0 e p , e quindi generare una permutazione da quel numero.

Generare il seme casuale è il tuo problema; Descrivo come trasformarlo in una permutazione nella mia lunga serie su proprietà interessanti di permutazioni, che puoi leggere qui:

link

Dubito che un tale PRNG esista, dal momento che semplicemente non è un buon PRNG. Non solo sai qualcosa del prossimo numero nella sequenza (mentre in un PRNG il punto è che non non sa nulla del prossimo numero), ma più a lungo la sequenza diventa, più sai!

Questo è solo un brutto PRNG.

Ciò di cui parli sembra essere più una permutazione (pseudo-) casuale che una sequenza di numeri casuali (pseudo-).

Un buon generatore di numeri pseudocasuali ha un ampio periodo, ad esempio L'implementazione di C # è superiore a 2⁵⁵

Dato che il prossimo numero intero sarà preso dall'insieme di valori di 2 ³², ci saranno ripetizioni molto prima che il suo periodo sia scaduto.