Números aleatorios únicos (no repetitivos) en O (1)?

Question

Me gustaría generar números aleatorios únicos entre 0 y 1000 que nunca se repitan (es decir, 6 no aparecen dos veces), pero eso no recurre a algo así como una búsqueda O (N) de valores previos para hacerlo . es posible?

Answer 1

Inicialice una matriz de 1001 enteros con los valores 0-1000 y establezca una variable, max, en el índice máximo actual de la matriz (comenzando por 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 regrese el número ahora en la posición max. Disminuir max por 1 y continuar. Cuando max es 0, ajuste max al tamaño de la matriz - 1 y comience nuevamente sin la necesidad de reiniciar la matriz.

Actualización: Aunque me ocurrió con este método por mi cuenta cuando me contestó la pregunta, después de algunas investigaciones me di cuenta que es una versión modificada del Fisher-Yates conocido como Durstenfeld-Fisher-Yates o Knuth-Fisher-Yates . Dado que la descripción puede ser un poco difícil de seguir, he proporcionado un ejemplo a continuación (usando 11 elementos en lugar de 1001):

La matriz comienza con 11 elementos inicializados en la matriz [n] = n, max 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, array [r] y array [max] se intercambian, se devuelve la nueva matriz [max], y max es decrementado:

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 han seleccionado todos los números en la matriz, máximo == 0, y la matriz de elementos se barajan:

+--+--+--+--+--+--+--+--+--+--+--+ 
| 4|10| 8| 6| 2| 0| 9| 5| 1| 7| 3| 
+--+--+--+--+--+--+--+--+--+--+--+ 

En este punto, max puede ser reajustado a 10 y el proceso puede continuar.

Answer 2

Usted puede hacer esto:

1. Crear una lista, 0..1000.
2. Baraja la lista. (Consulte Fisher-Yates shuffle para ver una buena forma de hacerlo).
3. Devuelva los números en orden desde la lista arrastrada.

Por lo tanto, esto no requiere una búsqueda de valores antiguos cada vez, pero todavía requiere O (N) para la reproducción inicial. Pero como señaló Nils en los comentarios, esto se amortiza O (1).

Answer 3

Otra posibilidad:

Puede usar una matriz de banderas. Y toma el siguiente cuando ya esté elegido.

Pero, tenga en cuenta después de 1000 llamadas, la función nunca terminará, por lo que debe hacer una salvaguarda.

Answer 4

Puede usar A Linear Congruential Generator. Donde m (el módulo) sería el primo más cercano más grande que 1000. Cuando obtienes un número fuera del rango, simplemente obtén el siguiente. La secuencia solo se repetirá una vez que se hayan producido todos los elementos, y usted no tiene que usar una tabla. Sin embargo, tenga en cuenta las desventajas de este generador (incluida la falta de aleatoriedad).

Answer 5

Utilice un Maximal Linear Feedback Shift Register.

Se puede implementar en unas pocas líneas de C y en el tiempo de ejecución hace poco más que un par de pruebas/ramas, una pequeña adición y cambio de bit. No es aleatorio, pero engaña a la mayoría de las personas.

Answer 6

Ni siquiera necesita una matriz para resolver esta.

Necesita una máscara de bits y un contador.

Inicialice el contador a cero e increméntelo en llamadas sucesivas. XOR el contador con la máscara de bits (seleccionada al azar al inicio, o fija) para generar un número psuedorandom. Si no puede tener números que excedan 1000, no use una máscara de bits de más de 9 bits. (En otras palabras, la máscara de bits es un número entero no superior a 511.)

Asegúrese de que cuando el contador pase 1000, restaure a cero. En este momento puede seleccionar otra máscara de bits aleatoria — si desea — para producir el mismo conjunto de números en un orden diferente.

Answer 7

Se podría utilizar una buena pseudo-random number generator con 10 bits y tirar 1001-1023 dejando 0 a 1000.

De here obtenemos el diseño de un PRNG de 10 bits ..

• 10 bits , polinomio de retroalimentación x^10 + x^7 + 1 (período de 1023)

• utilizar un Galois LFSR para obtener el código rápido

Answer 8

Para números bajos como 0 ... 1000, crear una lista que contenga todos los números y mezclarlos es sencillo. Pero si el conjunto de números para dibujar es muy grande, hay otra manera elegante: puede construir una permutación pseudoaleatoria utilizando una clave y una función de cifrado hash. Véase el siguiente C++ - ish ejemplo de código de pseudo:

unsigned randperm(string key, unsigned bits, unsigned index) { 
    unsigned half1 = bits /2; 
    unsigned half2 = (bits+1)/2; 
    unsigned mask1 = (1 << half1) - 1; 
    unsigned mask2 = (1 << half2) - 1; 
    for (int round=0; round<5; ++round) { 
    unsigned temp = (index >> half1); 
    temp = (temp << 4) + round; 
    index ^= hash(key + "/" + int2str(temp)) & mask1; 
    index = ((index & mask2) << half1) | ((index >> half2) & mask1); 
    } 
    return index; 
} 

Aquí, hash es sólo una función pseudo aleatoria arbitraria que asigna una cadena de caracteres a un enorme posiblemente entero sin signo. La función randperm es una permutación de todos los números dentro de 0 ... pow (2, bits) -1 asumiendo una clave fija. Esto se sigue de la construcción porque cada paso que cambia la variable index es reversible. Esto está inspirado en un Feistel cipher.

Answer 9

Aquí hay un código que escribí que usa la lógica de la primera solución. Sé que esto es "independiente del idioma", pero solo quería presentar esto como un ejemplo en C# en caso de que alguien esté buscando una solución práctica rápida.

// Initialize variables 
Random RandomClass = new Random(); 
int RandArrayNum; 
int MaxNumber = 10; 
int LastNumInArray; 
int PickedNumInArray; 
int[] OrderedArray = new int[MaxNumber];  // Ordered Array - set 
int[] ShuffledArray = new int[MaxNumber];  // Shuffled Array - not set 

// Populate the Ordered Array 
for (int i = 0; i < MaxNumber; i++)     
{ 
    OrderedArray[i] = i; 
    listBox1.Items.Add(OrderedArray[i]); 
} 

// Execute the Shuffle     
for (int i = MaxNumber - 1; i > 0; i--) 
{ 
    RandArrayNum = RandomClass.Next(i + 1);   // Save random # 
    ShuffledArray[i] = OrderedArray[RandArrayNum]; // Populting the array in reverse 
    LastNumInArray = OrderedArray[i];    // Save Last Number in Test array 
    PickedNumInArray = OrderedArray[RandArrayNum]; // Save Picked Random # 
    OrderedArray[i] = PickedNumInArray;    // The number is now moved to the back end 
    OrderedArray[RandArrayNum] = LastNumInArray; // The picked number is moved into position 
} 

for (int i = 0; i < MaxNumber; i++)     
{ 
    listBox2.Items.Add(ShuffledArray[i]); 
} 

Answer 10

Este método da como resultado apropiado cuando el límite es alta y sólo desea generar un par de números aleatorios.

#!/usr/bin/perl 

($top, $n) = @ARGV; # generate $n integer numbers in [0, $top) 

$last = -1; 
for $i (0 .. $n-1) { 
    $range = $top - $n + $i - $last; 
    $r = 1 - rand(1.0)**(1/($n - $i)); 
    $last += int($r * $range + 1); 
    print "$last ($r)\n"; 
} 

Tenga en cuenta que los números se generan en orden ascendente, pero luego puede mezclarlos.

Answer 11

public static int[] randN(int n, int min, int max) 
{ 
    if (max <= min) 
     throw new ArgumentException("Max need to be greater than Min"); 
    if (max - min < n) 
     throw new ArgumentException("Range needs to be longer than N"); 

    var r = new Random(); 

    HashSet<int> set = new HashSet<int>(); 

    while (set.Count < n) 
    { 
     var i = r.Next(max - min) + min; 
     if (!set.Contains(i)) 
      set.Add(i); 
    } 

    return set.ToArray(); 
} 

N Los números aleatorios no repetitivos serán de O (n) complejidad, según sea necesario.
Nota: Aleatorio debe ser estático con seguridad de hilo aplicada.

Answer 12

Puede usar Format-Preserving Encryption para encriptar un contador. Su contador simplemente va de 0 hacia arriba, y el cifrado utiliza una clave de su elección para convertirlo en un valor aparentemente aleatorio de cualquier raíz y ancho que desee. P.ej. para el ejemplo en esta pregunta: radix 10, ancho 3.

Los cifrados de bloque normalmente tienen un tamaño de bloque fijo de p. ej. 64 o 128 bits Pero el Cifrado de Preservación de Formato le permite tomar un cifrado estándar como AES y crear un cifrado de menor ancho, de cualquier radix y ancho que desee, con un algoritmo que sigue siendo criptográficamente robusto.

Se garantiza que nunca tendrá colisiones (porque los algoritmos criptográficos crean una asignación 1: 1). También es reversible (un mapeo bidireccional), por lo que puede tomar el número resultante y volver al valor del contador con el que comenzó.

Esta técnica no necesita memoria para almacenar una matriz mezclada, etc., que puede ser una ventaja en sistemas con memoria limitada.

AES-FFX es un método estándar propuesto para lograr esto. He experimentado con un código básico de Python que se basa en la idea de AES-FFX, aunque no totalmente conforme-- see Python code here. Puede, por ejemplo, cifra un contador a un número decimal de 7 dígitos de aspecto aleatorio o un número de 16 bits. Aquí está un ejemplo de radix 10, anchura 3 (para dar un número entre 0 y 999 inclusive) como la cuestión se indica:

000 733 
001 374 
002 882 
003 684 
004 593 
005 578 
006 233 
007 811 
008 072 
009 337 
010 119 
011 103 
012 797 
013 257 
014 932 
015 433 
... ... 

para obtener diferentes secuencias no repetir pseudo-aleatorios, cambiar la clave de cifrado. Cada clave de cifrado produce una secuencia pseudoaleatoria diferente no repetitiva.

Answer 13

Puedes usar mi algoritmo Xincrol describe aquí:

http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html

Este es un método algorítmico pura de generación de números aleatorios únicos, pero sin matrices, listas, permutaciones o pesada carga de la CPU.

La última versión también permite establecer el rango de números, por ejemplo, si quiero números aleatorios únicos en el rango de 0-1073741821.

he utilizado prácticamente por

• reproductor de MP3 que reproduce todas las canciones al azar, pero sólo una vez por cada disco/directorio
• Pixel fotogramas de vídeo sabios efecto de disolución (rápido y suave)
• Creación una niebla secreta de "ruido" sobre la imagen para firmas y marcadores (esteganografía)
• Id. de objeto de datos para la serialización de gran cantidad de objetos Java a través de bases de datos
• Bi memoria mayoritaria ts protection
• Encriptación de dirección + valor (cada byte no solo se cifra sino que se traslada a una nueva ubicación cifrada en el búfer). Esto realmente hizo que los tipos del criptoanálisis se enojaran conmigo :-)
• Texto simple a simple como Crypt Cifrado de texto para SMS, correos electrónicos, etc.
• mi Tejas Hold`em Poker Calculadora (THC)
• Varios de mis juegos de simulaciones, "arrastrando los pies", ocupando el
• más

Está abierto, libre. Pruébalo ...

Answer 14

Aquí hay un ejemplo de código COBOL con el que puedes jugar.
Puedo enviarle el archivo RANDGEN.exe para que pueda jugar con él y ver si quiere.

IDENTIFICATION DIVISION. 
    PROGRAM-ID. RANDGEN as "ConsoleApplication2.RANDGEN". 
    AUTHOR. Myron D Denson. 
    DATE-COMPILED. 
    * ************************************************************** 
    * SUBROUTINE TO GENERATE RANDOM NUMBERS THAT ARE GREATER THAN 
    * ZERO AND LESS OR EQUAL TO THE RANDOM NUMBERS NEEDED WITH NO 
    * DUPLICATIONS. (CALL "RANDGEN" USING RANDGEN-AREA.) 
    *  
    * CALLING PROGRAM MUST HAVE A COMPARABLE LINKAGE SECTION 
    * AND SET 3 VARIABLES PRIOR TO THE FIRST CALL IN RANDGEN-AREA  
    * 
    * FORMULA CYCLES THROUGH EVERY NUMBER OF 2X2 ONLY ONCE. 
    * RANDOM-NUMBERS FROM 1 TO RANDOM-NUMBERS-NEEDED ARE CREATED 
    * AND PASSED BACK TO YOU. 
    * 
    * RULES TO USE RANDGEN: 
    * 
    * RANDOM-NUMBERS-NEEDED > ZERO 
    *  
    * COUNT-OF-ACCESSES MUST = ZERO FIRST TIME CALLED. 
    *   
    * RANDOM-NUMBER = ZERO, WILL BUILD A SEED FOR YOU 
    * WHEN COUNT-OF-ACCESSES IS ALSO = 0 
    *  
    * RANDOM-NUMBER NOT = ZERO, WILL BE NEXT SEED FOR RANDGEN 
    * (RANDOM-NUMBER MUST BE <= RANDOM-NUMBERS-NEEDED)  
    *  
    * YOU CAN PASS RANDGEN YOUR OWN RANDOM-NUMBER SEED 
    *  THE FIRST TIME YOU USE RANDGEN. 
    *  
    * BY PLACING A NUMBER IN RANDOM-NUMBER FIELD 
    *  THAT FOLLOWES THESE SIMPLE RULES: 
    *  IF COUNT-OF-ACCESSES = ZERO AND 
    *  RANDOM-NUMBER > ZERO AND 
    *  RANDOM-NUMBER <= RANDOM-NUMBERS-NEEDED 
    *  
    * YOU CAN LET RANDGEN BUILD A SEED FOR YOU 
    *  
    *  THAT FOLLOWES THESE SIMPLE RULES: 
    *  IF COUNT-OF-ACCESSES = ZERO AND 
    *  RANDOM-NUMBER = ZERO AND 
    *  RANDOM-NUMBER-NEEDED > ZERO 
    *   
    *  TO INSURING A DIFFERENT PATTERN OF RANDOM NUMBERS 
    *  A LOW-RANGE AND HIGH-RANGE IS USED TO BUILD 
    *  RANDOM NUMBERS. 
    *  COMPUTE LOW-RANGE = 
    *    ((SECONDS * HOURS * MINUTES * MS)/3).   
    *  A HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE 
    *  AFTER RANDOM-NUMBER-BUILT IS CREATED 
    *  AND IS BETWEEN LOW AND HIGH RANGE 
    *  RANDUM-NUMBER = RANDOM-NUMBER-BUILT - LOW-RANGE 
    *    
    * **************************************************************   
    ENVIRONMENT DIVISION. 
    INPUT-OUTPUT SECTION. 
    FILE-CONTROL. 
    DATA DIVISION. 
    FILE SECTION. 
    WORKING-STORAGE SECTION. 
    01 WORK-AREA. 
     05 X2-POWER      PIC 9  VALUE 2. 
     05 2X2       PIC 9(12) VALUE 2 COMP-3. 
     05 RANDOM-NUMBER-BUILT   PIC 9(12) COMP. 
     05 FIRST-PART     PIC 9(12) COMP. 
     05 WORKING-NUMBER    PIC 9(12) COMP. 
     05 LOW-RANGE     PIC 9(12) VALUE ZERO. 
     05 HIGH-RANGE     PIC 9(12) VALUE ZERO. 
     05 YOU-PROVIDE-SEED    PIC X  VALUE SPACE. 
     05 RUN-AGAIN     PIC X  VALUE SPACE. 
     05 PAUSE-FOR-A-SECOND   PIC X  VALUE SPACE. 
    01 SEED-TIME. 
     05 HOURS      PIC 99. 
     05 MINUTES      PIC 99. 
     05 SECONDS      PIC 99. 
     05 MS       PIC 99. 
    * 
    * LINKAGE SECTION. 
    * Not used during testing 
    01 RANDGEN-AREA. 
     05 COUNT-OF-ACCESSES   PIC 9(12) VALUE ZERO. 
     05 RANDOM-NUMBERS-NEEDED  PIC 9(12) VALUE ZERO. 
     05 RANDOM-NUMBER    PIC 9(12) VALUE ZERO. 
     05 RANDOM-MSG     PIC X(60) VALUE SPACE. 
    *  
    * PROCEDURE DIVISION USING RANDGEN-AREA. 
    * Not used during testing 
    * 
    PROCEDURE DIVISION. 
    100-RANDGEN-EDIT-HOUSEKEEPING. 
     MOVE SPACE TO RANDOM-MSG. 
     IF RANDOM-NUMBERS-NEEDED = ZERO 
     DISPLAY 'RANDOM-NUMBERS-NEEDED ' NO ADVANCING 
     ACCEPT RANDOM-NUMBERS-NEEDED. 
     IF RANDOM-NUMBERS-NEEDED NOT NUMERIC 
     MOVE 'RANDOM-NUMBERS-NEEDED NOT NUMERIC' TO RANDOM-MSG 
      GO TO 900-EXIT-RANDGEN. 
     IF RANDOM-NUMBERS-NEEDED = ZERO 
     MOVE 'RANDOM-NUMBERS-NEEDED = ZERO' TO RANDOM-MSG 
      GO TO 900-EXIT-RANDGEN. 
     IF COUNT-OF-ACCESSES NOT NUMERIC 
     MOVE 'COUNT-OF-ACCESSES NOT NUMERIC' TO RANDOM-MSG 
      GO TO 900-EXIT-RANDGEN. 
     IF COUNT-OF-ACCESSES GREATER THAN RANDOM-NUMBERS-NEEDED 
     MOVE 'COUNT-OF-ACCESSES > THAT RANDOM-NUMBERS-NEEDED' 
      TO RANDOM-MSG 
      GO TO 900-EXIT-RANDGEN. 
     IF YOU-PROVIDE-SEED = SPACE AND RANDOM-NUMBER = ZERO 
     DISPLAY 'DO YOU WANT TO PROVIDE SEED Y OR N: ' 
      NO ADVANCING 
      ACCEPT YOU-PROVIDE-SEED. 
     IF RANDOM-NUMBER = ZERO AND 
      (YOU-PROVIDE-SEED = 'Y' OR 'y') 
     DISPLAY 'ENTER SEED ' NO ADVANCING 
     ACCEPT RANDOM-NUMBER. 
     IF RANDOM-NUMBER NOT NUMERIC 
     MOVE 'RANDOM-NUMBER NOT NUMERIC' TO RANDOM-MSG 
     GO TO 900-EXIT-RANDGEN. 
    200-RANDGEN-DATA-HOUSEKEEPING.  
     MOVE FUNCTION CURRENT-DATE (9:8) TO SEED-TIME. 
     IF COUNT-OF-ACCESSES = ZERO 
     COMPUTE LOW-RANGE = 
       ((SECONDS * HOURS * MINUTES * MS)/3). 
     COMPUTE RANDOM-NUMBER-BUILT = RANDOM-NUMBER + LOW-RANGE. 
     COMPUTE HIGH-RANGE = RANDOM-NUMBERS-NEEDED + LOW-RANGE. 
     MOVE X2-POWER TO 2X2.    
    300-SET-2X2-DIVISOR. 
     IF 2X2 < (HIGH-RANGE + 1) 
      COMPUTE 2X2 = 2X2 * X2-POWER 
      GO TO 300-SET-2X2-DIVISOR.  
    * *********************************************************   
    * IF FIRST TIME THROUGH AND YOU WANT TO BUILD A SEED. * 
    * ********************************************************* 
     IF COUNT-OF-ACCESSES = ZERO AND RANDOM-NUMBER = ZERO 
      COMPUTE RANDOM-NUMBER-BUILT = 
       ((SECONDS * HOURS * MINUTES * MS) + HIGH-RANGE). 
     IF COUNT-OF-ACCESSES = ZERO   
     DISPLAY 'SEED TIME ' SEED-TIME 
       ' RANDOM-NUMBER-BUILT ' RANDOM-NUMBER-BUILT 
       ' LOW-RANGE ' LOW-RANGE.   
    * *********************************************  
    * END OF BUILDING A SEED IF YOU WANTED TO * 
    * *********************************************    
    * *************************************************** 
    * THIS PROCESS IS WHERE THE RANDOM-NUMBER IS BUILT * 
    * *************************************************** 
    400-RANDGEN-FORMULA. 
     COMPUTE FIRST-PART = (5 * RANDOM-NUMBER-BUILT) + 7. 
     DIVIDE FIRST-PART BY 2X2 GIVING WORKING-NUMBER 
     REMAINDER RANDOM-NUMBER-BUILT. 
     IF RANDOM-NUMBER-BUILT > LOW-RANGE AND 
      RANDOM-NUMBER-BUILT < (HIGH-RANGE + 1) 
     GO TO 600-RANDGEN-CLEANUP. 
     GO TO 400-RANDGEN-FORMULA. 
    * *********************************************  
    * GOOD RANDOM NUMBER HAS BEEN BUILT  *    
    * ********************************************* 
    600-RANDGEN-CLEANUP. 
     ADD 1 TO COUNT-OF-ACCESSES. 
     COMPUTE RANDOM-NUMBER = 
      RANDOM-NUMBER-BUILT - LOW-RANGE. 
    * ******************************************************* 
    * THE NEXT 3 LINE OF CODE ARE FOR TESTING ON CONSOLE * 
    * ******************************************************* 
     DISPLAY RANDOM-NUMBER. 
     IF COUNT-OF-ACCESSES < RANDOM-NUMBERS-NEEDED 
     GO TO 100-RANDGEN-EDIT-HOUSEKEEPING.  
    900-EXIT-RANDGEN. 
     IF RANDOM-MSG NOT = SPACE 
     DISPLAY 'RANDOM-MSG: ' RANDOM-MSG. 
     MOVE ZERO TO COUNT-OF-ACCESSES RANDOM-NUMBERS-NEEDED RANDOM-NUMBER. 
     MOVE SPACE TO YOU-PROVIDE-SEED RUN-AGAIN. 
     DISPLAY 'RUN AGAIN Y OR N ' 
     NO ADVANCING. 
     ACCEPT RUN-AGAIN. 
     IF (RUN-AGAIN = 'Y' OR 'y') 
     GO TO 100-RANDGEN-EDIT-HOUSEKEEPING. 
     ACCEPT PAUSE-FOR-A-SECOND. 
     GOBACK. 

Answer 15

La mayoría de las respuestas aquí no garantizan que no devolverán el mismo número dos veces. Aquí hay una solución correcta:

int nrrand(void) { 
    static int s = 1; 
    static int start = -1; 
    do { 
    s = (s * 1103515245 + 12345) & 1023; 
    } while (s >= 1001); 
    if (start < 0) start = s; 
    else if (s == start) abort(); 

    return s; 
} 

No estoy seguro de que la restricción esté bien especificada. Se supone que después de 1000 otras salidas se permite que un valor se repita, pero ingenuamente permite que 0 siga inmediatamente después de 0, siempre y cuando ambos aparezcan al final y comiencen los conjuntos de 1000. Por el contrario, aunque es posible mantener una distancia de 1000 otros valores entre repeticiones, al hacerlo, fuerza una situación en la que la secuencia se repite exactamente de la misma manera cada vez porque no hay otro valor que haya ocurrido fuera de ese límite.

Aquí es un método que garantiza siempre por lo menos otros 500 valores antes de un valor se puede repetir:

int nrrand(void) { 
    static int h[1001]; 
    static int n = -1; 

    if (n < 0) { 
    int s = 1; 
    for (int i = 0; i < 1001; i++) { 
     do { 
     s = (s * 1103515245 + 12345) & 1023; 
     } while (s >= 1001); 
     /* If we used `i` rather than `s` then our early results would be poorly distributed. */ 
     h[i] = s; 
    } 
    n = 0; 
    } 

    int i = rand(500); 
    if (i != 0) { 
     i = (n + i) % 1001; 
     int t = h[i]; 
     h[i] = h[n]; 
     h[n] = t; 
    } 
    i = h[n]; 
    n = (n + 1) % 1001; 

    return i; 
} 

Answer 16

Digamos que usted quiere ir más barajado listas de una y otra, sin tener el retraso O(n) cada vez que se empezar de nuevo a barajar de nuevo, en ese caso podemos hacer esto:

1. crear 2 listas a y B, con 0 a 1000, toma 2n espacio.

2. Lista aleatoria A usando Fisher-Yates, toma n tiempo.

3. Al dibujar un número, realice una compilación de Fisher-Yates de 1 paso en la otra lista.

4. Cuando el cursor está al final de la lista, cambie a la otra lista.

preproceso

cursor = 0 

selector = A 
other = B 

shuffle(A) 

Dibuje

temp = selector[cursor] 

swap(other[cursor], other[random]) 

if cursor == N 
then swap(selector, other); cursor = 0 
else cursor = cursor + 1 

return temp 

Answer 17

Cuando N es mayor que 1000 y que necesita para llamar la K muestras aleatorias se puede utilizar un conjunto que contiene las muestras hasta aquí. Para cada sorteo, usa rejection sampling, que será una operación "casi" O (1), por lo que el tiempo de ejecución total es casi O (K) con O (N) almacenamiento.

Este algoritmo se encuentra con colisiones cuando K está "cerca" de N. Esto significa que el tiempo de ejecución será mucho peor que O (K). Una solución simple es invertir la lógica para que, para K> N/2, conserve un registro de todas las muestras que aún no se han dibujado. Cada extracción elimina una muestra del conjunto de rechazo.

El otro problema obvio con el muestreo de rechazo es que es O (N) almacenamiento, lo cual es una mala noticia si N es de los miles de millones o más. Sin embargo, hay un algoritmo que resuelve ese problema. Este algoritmo se llama algoritmo de Vitter después de su inventor. El algoritmo se describe here. La esencia del algoritmo de Vitter es que después de cada extracción, calcula un salto al azar usando una distribución determinada que garantiza un muestreo uniforme.

Answer 18

Creo que Linear congruential generator sería la solución más simple.

y sólo hay 3 restricciones en los un, c y m valores

1. m y c son relativamente primos,
2. a-1 es divisible por todos los factores primos de m
3. a-1 es divisible por if m es divisible por

PS el método ya se ha mencionado, pero el Post dispone de un suposiciones erróneas acerca de los valores constantes. Las constantes continuación deben funcionar bien para su caso

En su caso, usted puede usar a = 1002, c = 757, m = 1001

X = (1002 * X + 757) mod 1001 

Answer 19

Fisher Yates

for i from n−1 downto 1 do 
    j ← random integer such that 0 ≤ j ≤ i 
    exchange a[j] and a[i] 

En realidad, es O (n-1) mientras solo necesita un intercambio para los dos últimos
Esto es C#

Answer 20

La pregunta How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N está vinculada como un duplicado, y si quiere algo que es O (1) por número aleatorio generado (sin costo de inicio de O (n)), hay un simple ajuste de la respuesta aceptada.

Crea un mapa desordenado vacío (un mapa ordenado vacío tomará O (log k) por elemento) de entero a entero, en lugar de utilizar una matriz inicializada. Establezca max a 1000 si ese es el máximo,

1. Elija un número aleatorio, r, entre 0 y máx.
2. Asegúrese de que ambos elementos r y max del mapa existan en el mapa desordenado. Si no existen, créelos con un valor igual a su índice.
3. elementos Intercambia r y máximo
4. elemento de retorno y máximo decremento máximo en 1 (máx si se hace negativa haya terminado).
5. Volver al paso 1.

La única diferencia en comparación con el uso de una matriz inicializada es que la inicialización de los elementos se pospone/saltado - pero generará exactamente los mismos números de la misma PRNG.

Answer 21

favor ver mi respuesta a https://stackoverflow.com/a/46807110/8794687

Es uno de los algoritmos más simples que tienen complejidad O tiempo promedio (s registro s), s denota el tamaño de la muestra. También hay algunos enlaces a algoritmos de tablas hash cuya complejidad se afirma que es O (s).