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

Me gustaría generar números aleatorios únicos entre 0 y 1000 que nunca se repiten (es decir, 6 no aparece dos veces), pero eso no recurre 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, max, 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 max en 1 y continúe. Cuando max es 0, vuelva a establecer max al tamaño de la matriz - 1 y comience nuevamente sin la necesidad de reiniciar la matriz.

Actualización: aunque se me ocurrió este método por mi cuenta cuando respondí la pregunta, después de algunas investigaciones me doy cuenta de que esta es 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, 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, 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 han seleccionado todos los números de la matriz, max == 0, y los elementos de la matriz se barajan:

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

En este punto, max se puede restablecer a 10 y el proceso puede continuar.

Puedes hacerlo:

1. Crea una lista, 0..1000.
2. Baraja la lista. (Ver Fisher-Yates shuffle para una buena manera de hacer esto).
3. 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 combinación 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 .

Es implementable 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 desplazamiento. No es al azar, pero engaña a la mayoría de las personas.

Podría usar un generador congruencial lineal . Donde m(el módulo) sería el primo más cercano mayor que 1000. Cuando obtenga un número fuera del rango, simplemente obtenga el siguiente. La secuencia solo se repetirá una vez que se hayan producido todos los elementos y no tenga que usar una tabla. Sin embargo, tenga en cuenta las desventajas de este generador (incluida la falta de aleatoriedad).

Puede usar el cifrado de preservación de formato para cifrar un contador. Su contador solo va de 0 en adelante, y el cifrado utiliza una clave de su elección para convertirlo en un valor aparentemente aleatorio de la raíz y el ancho que desee. Por ejemplo, para el ejemplo en esta pregunta: radix 10, ancho 3.

Los cifrados de bloque normalmente tienen un tamaño de bloque fijo de, por ejemplo, 64 o 128 bits. Pero Format-Preserving Encryption le permite tomar un cifrado estándar como AES y hacer un cifrado de menor ancho, de cualquier radix y ancho que desee, con un algoritmo que todavía es criptográficamente robusto.

Se garantiza que nunca tendrá colisiones (porque los algoritmos criptográficos crean un mapeo 1: 1). También es reversible (un mapeo de 2 vías), 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 aleatoria, etc., lo que puede ser una ventaja en sistemas con memoria limitada.

AES-FFX es un método estándar propuesto para lograr esto. Experimenté con un código básico de Python que se basa en la idea de AES-FFX, aunque no es totalmente compatible; vea el código de Python aquí . Puede, por ejemplo, encriptar un contador a un número decimal de 7 dígitos de aspecto aleatorio, o un número de 16 bits. Aquí hay un ejemplo de radix 10, ancho 3 (para dar un número entre 0 y 999 inclusive) como dice la pregunta:

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 pseudoaleatorias no repetitivas, cambie la clave de cifrado. Cada clave de cifrado produce una secuencia pseudoaleatoria no repetitiva diferente.

Para números bajos como 0 ... 1000, crear una lista que contenga todos los números y barajarlo es sencillo. Pero si el conjunto de números para extraer es muy grande, hay otra forma elegante: puede construir una permutación pseudoaleatoria usando una clave y una función hash criptográfica. Consulte el siguiente pseudocódigo de ejemplo C ++ - ish:

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í hashhay una función pseudoaleatoria arbitraria que asigna una cadena de caracteres a un entero sin signo posiblemente enorme. La función randpermes una permutación de todos los números dentro de 0 ... pow (2, bits) -1 suponiendo una clave fija. Esto se desprende de la construcción porque cada paso que cambia la variable indexes reversible. Esto está inspirado en un cifrado Feistel .

Puede usar mi algoritmo Xincrol descrito aquí:

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

Este es un método algorítmico puro para generar números aleatorios pero únicos sin matrices, listas, permutaciones o una gran carga de 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.

Prácticamente lo he usado para

• Reproductor de MP3 que reproduce cada canción al azar, pero solo una vez por álbum / directorio
• Efecto de disolución de fotogramas de video inteligente en píxeles (rápido y suave)
• Crear una niebla secreta de "ruido" sobre la imagen para firmas y marcadores (esteganografía)
• ID de objetos de datos para la serialización de una gran cantidad de objetos Java a través de bases de datos
• Protección de bits de memoria de triple mayoría
• Cifrado de dirección + valor (cada byte no solo se cifra sino que también se mueve a una nueva ubicación cifrada en el búfer). Esto realmente enfureció a los tipos de criptoanálisis :-)
• Cifrado de texto sin formato a cifrado de texto simple para SMS, correos electrónicos, etc.
• Mi calculadora de póker Texas Hold`em (THC)
• Varios de mis juegos para simulaciones, "barajar", clasificación
• más

Es abierto, gratis. Darle una oportunidad...

Ni siquiera necesita una matriz para resolver este.

Necesitas 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 aleatoriamente al inicio o fijada) para generar un número psuedorandom. Si no puede tener números que excedan 1000, no use una máscara de bits más ancha que 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, lo restablezca a cero. En este momento, puede seleccionar otra máscara de bits aleatoria, si lo desea, para producir el mismo conjunto de números en un orden diferente.

Creo que el generador congruencial lineal sería la solución más simple.

y sólo hay 3 restricciones a la una , 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 4 si m es divisible por 4

PD: el método ya se mencionó, pero la publicación tiene supuestos erróneos sobre los valores constantes. Las constantes a continuación deberían funcionar bien para su caso

En su caso, es posible utilizar a = 1002, c = 757,m = 1001

X = (1002 * X + 757) mod 1001

Aquí hay un código que escribí que usa la lógica de la primera solución. Sé que esto es "independiente del lenguaje", 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]);
}

Este método resulta apropiado cuando el límite es alto y solo desea generar algunos 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 puede barajarlos luego.

Podría usar un buen generador de números pseudoaleatorios con 10 bits y tirar 1001 a 1023 dejando 0 a 1000.

Desde aquí obtenemos el diseño para un PRNG de 10 bits.

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

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

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 repetidos serán de complejidad O (n), según se requiera.
Nota: Aleatorio debe ser estático con seguridad de hilo aplicada.

Digamos que desea repasar las listas barajadas una y otra vez, sin tener el O(n)retraso cada vez que comience a barajarlas nuevamente, en ese caso podemos hacer esto:

1. Crear 2 listas A y B, con 0 a 1000, ocupa 2nespacio.

2. La lista aleatoria A con Fisher-Yates lleva ntiempo.

3. Cuando dibuje un número, haga barajar 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)

Dibujar

temp = selector[cursor]

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

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

return temp

La pregunta ¿Cómo genera eficientemente una lista de K enteros no repetidos entre 0 y un límite superior N está vinculado como un duplicado, y si desea algo que sea O (1) por número aleatorio generado (sin O (n) costo de inicio)) hay un simple ajuste de la respuesta aceptada.

Cree un mapa vacío desordenado (un mapa ordenado vacío tomará O (log k) por elemento) de entero a entero, en lugar de usar 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 del mapa r y max existan en el mapa desordenado. Si no existen, créelos con un valor igual a su índice.
3. Intercambiar elementos r y max
4. Devuelve el elemento max y disminuye max en 1 (si max se vuelve negativo, ya está).
5. Regresar al paso 1.

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

Otra posibilidad:

Puedes usar una variedad de banderas. Y tome el siguiente cuando ya esté elegido.

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

Aquí hay un código COBOL de muestra con el que puedes jugar.
Puedo enviarle el archivo RANDGEN.exe para que pueda jugar con él y ver si quiere lo que 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.

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 otras 1000 salidas se permite repetir un valor, pero ingenuamente permite que 0 siga inmediatamente después de 0, siempre que ambas aparezcan al final y al comienzo de las series de 1000. Por el contrario, es posible mantener una distancia de 1000 otros valores entre repeticiones, al hacerlo, se 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í hay un método que siempre garantiza al menos otros 500 valores antes de que se pueda repetir un valor:

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;
}

Cuando N es mayor que 1000 y necesita dibujar K muestras aleatorias, puede usar un conjunto que contenga las muestras hasta ahora. Para cada sorteo, utiliza el muestreo de rechazo , que será una operación "casi" O (1), por lo que el tiempo total de ejecución es casi O (K) con almacenamiento O (N).

Este algoritmo se topa 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, mantenga un registro de todas las muestras que aún no se han extraído. Cada dibujo elimina una muestra del conjunto de rechazo.

El otro problema obvio con el muestreo de rechazo es que es el almacenamiento de O (N), lo cual es una mala noticia si N está en 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. Se describe el algoritmo. aquí . La esencia del algoritmo de Vitter es que, después de cada sorteo, calcula un salto aleatorio utilizando una cierta distribución que garantiza un muestreo uniforme.

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) ya que solo necesita un intercambio para los dos últimos.
Esto es C #

public static List<int> FisherYates(int n)
{
    List<int> list = new List<int>(Enumerable.Range(0, n));
    Random rand = new Random();
    int swap;
    int temp;
    for (int i = n - 1; i > 0; i--)
    {
        swap = rand.Next(i + 1);  //.net rand is not inclusive
        if(swap != i)  // it can stay in place - if you force a move it is not a uniform shuffle
        {
            temp = list[i];
            list[i] = list[swap];
            list[swap] = temp;
        }
    }
    return list;
}

Por favor vea mi respuesta en https://stackoverflow.com/a/46807110/8794687

Es uno de los algoritmos más simples que tienen tiempo medio de complejidad O ( 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 ).

Alguien publicó "creando números aleatorios en Excel". Estoy usando este ideal. Cree una estructura con 2 partes, str.index y str.ran; Para 10 números aleatorios, cree una matriz de 10 estructuras. Establezca str.index de 0 a 9 y str.ran en un número aleatorio diferente.

for(i=0;i<10; ++i) {
      arr[i].index = i;
      arr[i].ran   = rand();
}

Ordene la matriz según los valores en arr [i] .ran. El str.index ahora está en un orden aleatorio. A continuación se muestra el código c:

#include <stdio.h>
#include <stdlib.h>

struct RanStr { int index; int ran;};
struct RanStr arr[10];

int sort_function(const void *a, const void *b);

int main(int argc, char *argv[])
{
   int cnt, i;

   //seed(125);

   for(i=0;i<10; ++i)
   {
      arr[i].ran   = rand();
      arr[i].index = i;
      printf("arr[%d] Initial Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   qsort( (void *)arr, 10, sizeof(arr[0]), sort_function);
   printf("\n===================\n");
   for(i=0;i<10; ++i)
   {
      printf("arr[%d] Random  Order=%2d, random=%d\n", i, arr[i].index, arr[i].ran);
   }

   return 0;
}

int sort_function(const void *a, const void *b)
{
   struct RanStr *a1, *b1;

   a1=(struct RanStr *) a;
   b1=(struct RanStr *) b;

   return( a1->ran - b1->ran );
}