Penso che qualcosa non sia chiaro nella domanda. Stai chiedendo:
1) Posso generare un gran numero di permutazioni casuali di 4000000 elementi usando un PRNG, dove un numero elevato è qualcosa come 100000000000 permutazioni casuali?
o
2) Posso generare OGNI permutazione casuale di 4000000 elementi usando un PRNG?
La risposta alla prima domanda è sì, e alla seconda domanda c'è no. Prendi Mersenne Twister come esempio. Per generare una permutazione casuale, è necessario generare 8.1e + 7 bit casuali, o circa 2 ^ 21 numeri casuali a 32 bit. Dal momento che il periodo di Mersenne Twister è 2 ^ 19997, puoi continuare e generare un enorme 2 ^ 19976 permutazioni casuali, molte di più di quelle di cui avrai mai bisogno.
Tuttavia, se si desidera generare OGNI eventuale permutazione casuale, è necessario generare almeno 2 ^ 8100000 permutazioni casuali, che è maggiore di 2 ^ 19976. Ma non c'è alcuna ragione pratica per generare ogni possibile permutazione.
Per quanto riguarda l'altra domanda nei commenti sul fatto che uno shuffle casuale possa campionare uniformemente da tutte le possibili permutazioni: la risposta è sì. Finché il tuo RNG può generare 80000000 bit consecutivi uniformemente casuali, che può essere Mersenne Twister, il tuo campionamento sarà uniforme.