Volviendo entero aleatorio del intervalo basado en el último resultado y una semilla

Question

Supongamos que tenemos un intervalo de enteros [a, b].Me gustaría tener una función que devuelva a los miembros aleatorios desde el intervalo, sin repeticiones.Una vez que se exploren todos los miembros dentro del intervalo, la función comenzaría a devolver la misma primera secuencia aleatoria nuevamente, en el mismo orden.

Ejemplo: A= 1, B= 5

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

Esto sería fácil de lograr al arrastrar una matriz de todos los elementos entre A y B, y repetirlo una vez que se termine la matriz.Sin embargo, esto tomaría demasiado espacio de memoria, y esto no es adecuado para mi caso (podría tener millones de elementos).

En su lugar, la función que me gustaría tener sería más o menos así:

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

donde:

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)

El truco es saber alguna forma de obtener un número no repetido del intervalo basado solo en el elemento devuelto antes y la semilla.Al final, se comportaría como una lista circular aleatorizada en su inicialización, pero sin usar espacio de memoria.

Answer 1

Le sugiero que seleccione una permutación aleatoria en el rango $ [a, b] $ , es decir, una función biquilivista $ \ PI: [a, b] \ a [a, b] $ . Luego, mantenga un contador $ i $ que comienza en $ i= A $ ; En cada paso, salida $ \ pi (i) $ y luego incremento $ i $ (envolviendo por lo que que $ b + 1 $ se convierte en $ a $ ).

Hay métodos estándar para generar una permutación tan aleatoria en la literatura de la criptografía: busque el cifrado de conservación de formatos. La semilla es la clave criptográfica. Podrá calcular $ \ pi (i) $ en $ o (1) $ tiempo y $ o (1) $ espacio, por lo que esto debería ser muy eficiente y evitar la necesidad de un montón de almacenamiento.

Si insistía en que la siguiente salida debe ser una función de la salida anterior, puede permitir que $ g (i)= i + 1 $ (excepto que < Span Class="Math-contenedor"> $ g (b)= A $ ), luego deja $ f (i)=pi ^ {- 1} (g (\ PI (i)) $ , donde $ \ pi $ es una permutación aleatoria elegida como la anterior. Esto le dará un ciclo aleatorio que itera. a través de los elementos de $ [a, b] $ en un orden aleatorio. Las salidas son la secuencia $ f (a) , f (f (a)), f (f (f (a))), \ puntos $ .