Pigramente calcolo di una permutazione casuale di numeri interi positivi

Question

Ci sono esistenti algoritmi efficienti per pigramente calcolo di una permutazione casuale di numeri interi positivi in un dato intervallo (es.la gamma offerta da un tipo unsigned integer in una CPU)?

Quello che voglio dire è questo:

Un algoritmo che, data una sorgente di casualità e di un numero intero positivo gamma (per semplicità si potrebbe essere limitato a partire da 0 e termina a n), può essere chiesto di produrre la prossima valore nell'intervallo.Questo può essere ripetuto n volte, e un numero diverso è fornito dall'algoritmo di ogni tempo.

Se il chiamante sono stati per spingere tutti i valori recuperati dall'algoritmo in una coda risultante ordine sarebbe altrettanto casuale come se il risultato fosse stato generato con lo shuffle Fisher–Yates.

L'ingenuo attuazione sarebbe quello di scegliere un numero casuale nell'intervallo, controllare per vedere se è già stato selezionato e scegliere di nuovo, se è così.Questo algoritmo inizia abbastanza efficiente, ma ha una complessità crescente per le chiamate successive, troppo costoso per le applicazioni del mondo reale.Per essere davvero utili dovrebbe essere O(1) per ogni prova, anche se un buon tempo logaritmico potrebbe essere applicabile.

Deve essere pigri, perché con i valori di grandi dimensioni (come una versione a 64 bit unsigned integer) sarebbe Exabyte di archiviazione di precalcolare tutta la permutazione, ed è improbabile che un'applicazione reale è veramente bisogno di tutta la gamma;semplicemente ha bisogno che l'intera gamma è stata considerata in valori che essa è in realtà andando a utilizzare.

Essenzialmente il problema è solo pigramente la generazione di un mapping tra i numeri interi in una gamma e una permutazione casuale di quegli stessi numeri interi, pur essendo in grado di accedere alla mappatura in punti arbitrari invece che solo in modo sequenziale, ma è un bonus.