¿Números aleatorios únicos (no repetidos) en O (1)?
Me gustaría generar números aleatorios únicos entre 0 y 1000 que nunca se repitan (es decir, 6 no aparece dos veces), pero que no recurran a algo como una búsqueda O(N) de valores anteriores para hacerlo. es posible?
Inicialice una matriz de 1001 enteros con los valores 0-1000 y establezca una variable, máx, en el índice máximo actual de la matriz (comenzando con 1000). Elija un número aleatorio, r, entre 0 y max, intercambie el número en la posición r con el número en la posición max y devuelva el número ahora en la posición max. Disminuya el máximo en 1 y continúe. Cuando max es 0, vuelva a establecer max al tamaño de la matriz: 1 y comience de nuevo sin la necesidad de reinicializar la matriz.
Actualización: aunque se me ocurrió este método por mi cuenta cuando respondí la pregunta, después de investigar un poco me doy cuenta de que se trata de una versión modificada de Fisher-Yates conocida como Durstenfeld-Fisher-Yates o Knuth-Fisher-Yates. Dado que la descripción puede ser un poco difícil de seguir, proporcioné un ejemplo a continuación (usando 11 elementos en lugar de 1001):
La matriz comienza con 11 elementos inicializados en matriz[n] = n, el máximo comienza en 10:
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
^
max
En cada iteración, se selecciona un número aleatorio r entre 0 y max, se intercambian la matriz[r] y la matriz[max], se devuelve la nueva matriz[max] y se disminuye max:
max = 10, r = 3
+--------------------+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 7| 8| 9| 3|
+--+--+--+--+--+--+--+--+--+--+--+
max = 9, r = 7
+-----+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2|10| 4| 5| 6| 9| 8| 7: 3|
+--+--+--+--+--+--+--+--+--+--+--+
max = 8, r = 1
+--------------------+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 5| 6| 9| 1: 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+
max = 7, r = 5
+-----+
v v
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 8| 2|10| 4| 9| 6| 5: 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+
...
Después de 11 iteraciones, se seleccionaron todos los números de la matriz, máx == 0, y los elementos de la matriz se mezclaron:
+--+--+--+--+--+--+--+--+--+--+--+
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3|
+--+--+--+--+--+--+--+--+--+--+--+
En este punto, el máximo se puede restablecer a 10 y el proceso puede continuar.
Puedes hacerlo:
- Crea una lista, 0..1000.
- Mezcla la lista. (Consulte la reproducción aleatoria de Fisher-Yates para conocer una buena forma de hacerlo).
- Devuelve los números en orden de la lista aleatoria.
Por lo tanto, esto no requiere una búsqueda de valores antiguos cada vez, pero aún requiere O(N) para la mezcla inicial. Pero como Nils señaló en los comentarios, esto se amortiza O(1).
Utilice un registro de desplazamiento de retroalimentación lineal máxima .
Se puede implementar en unas pocas líneas de C y en tiempo de ejecución hace poco más que un par de pruebas/ramas, una pequeña adición y un poco de cambio. No es aleatorio, pero engaña a la mayoría de la gente.
