Tornando il numero intero casuale dall'intervallo in base all'ultimo risultato e da un seme

Question

Supponiamo di avere un intervallo di interi [A, B].Mi piacerebbe avere una funzione che restituisca i membri casuali dall'intervallo, senza ripetizioni.Una volta esplorato tutti i membri all'interno dell'intervallo, la funzione avrebbe iniziato a restituire nuovamente la stessa sequenza casuale, nello stesso ordine.

Esempio: A= 1, B= 5

3, 1, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 2, ...

.

Questo sarebbe facile da ottenere mescolare una serie di tutti gli elementi tra A e B e ripetendolo una volta terminato l'array.Tuttavia, questo richiederebbe troppo spazio di memoria, e questo non è adatto per il mio caso (potrei avere milioni di elementi).

Invece, la funzione che vorrei avere sarebbe più o meno in questo modo:

f(a, b, n, seed) -> n+1

.

Dove:

a - start of interval
b - end of interval
n - last element returned from list
seed - self-explanatory
n+1 - next random element from list, calculated by using the seed and the last element returned (n)

.

Il trucco è conoscere un modo per ottenere un numero non ripetuto dall'intervallo basato solo sull'elemento restituito prima e il seme.Alla fine, si comporterebbe come una lista circolare randomizzata alla sua inizializzazione, ma senza utilizzare lo spazio di memoria.

Answer 1

Ti suggerisco di scegliere un permutazione casuale sulla gamma $ [A, B] $ , cioè una funzione Bijective $ \ PI: [a, b] \ a [a, b] $ . Quindi, mantenere un contatore $ i $ che inizia a $ i= un $ ; Ad ogni passaggio, output $ \ PI (i) $ e quindi incremento $ I $ (avvolgendo così Quella $ B + 1 $ diventa $ a $ ).

Ci sono metodi standard per la generazione di tale permutazione casuale nella letteratura della crittografia: cercare la crittografia di conservazione del formato. Il seme è la chiave crittografica. Sarai in grado di calcolare $ \ pi (i) $ in $ o (1) $ tempo e $ O (1) $ spazio, quindi questo dovrebbe essere molto efficiente ed evitare la necessità di un sacco di spazio.

Se insistono che la successiva uscita dovrebbe essere una funzione dell'output precedente, è possibile lasciare $ g (i)= I + 1 $ (tranne che < Span Class="Math-Container"> $ G (B)= A $ ), quindi lasciare $ f (i)=pi ^ {- 1} (G (\ pi (i)) $ , dove $ \ PI $ è un permutazione casuale scelto come sopra. Questo ti darà un ciclo casuale che itera attraverso gli elementi di $ [a, b] $ in un ordine casuale. Le uscite sono la sequenza $ f (A) , f (f (A)), f (f (f (A))), \ punti $ .