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

Puedes hacer esto:

1. Crea una lista, 0..1000.
2. Barajar la lista. (Ver Fisher-Yates shuffle para una buena manera de hacer esto.)
3. Devuelve los números en orden desde la lista barajada.

Así que esto no requiere una búsqueda de valores antiguos cada vez, pero todavía 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 .

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 desplazamiento de bits. No es al azar, pero engaña a la mayoría de la gente.

Podría usar Un Generador Congruente Lineal . Donde m (el módulo) sería el primo más cercano mayor que 1000. Cuando usted consigue un número fuera de la gama, acaba de conseguir el siguiente. La secuencia solo se repetirá una vez que se hayan producido todos los elementos, y no es necesario usar una tabla. Sin embargo, tenga en cuenta las desventajas de este generador (incluida la falta de aleatoriedad).

Puede usar Cifrado que preserva el formato para cifrar 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 radio y ancho que desee. Por ejemplo, para el ejemplo de 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 el cifrado que preserva el formato le permite tomar un cifrado estándar como AES y hacer un cifrado de menor ancho, de cualquier radio 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 (una asignación 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 barajada, etc., lo que puede ser una ventaja en sistemas con limitaciones memoria.

AES-FFX es un método estándar propuesto para lograr esto. He experimentado con código Python básico que se basa en la idea de AES-FFX, aunque no totalmente conforme {ver código Python aquí . Puede, por ejemplo, cifrar 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 la pregunta declaró:

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 no repeticiones secuencias pseudo-aleatorias, cambiar la clave de cifrado. Cada clave de cifrado produce una secuencia pseudo-aleatoria diferente que no se repite.

Para números bajos como 0...1000, crear una lista que contenga todos los números y barajarla es sencillo. Pero si el conjunto de números para dibujar es muy grande, hay otra forma elegante: Puedes construir una permutación pseudoaleatoria usando una clave y una función hash criptográfica. Vea el siguiente pseudo código de ejemplo de 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í, hash es solo una función pseudo aleatoria arbitraria que asigna una cadena de caracteres a un número entero sin signo posiblemente enorme. 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 desprende de la construcción porque cada paso que cambia la variable index es reversible. Esto está inspirado en un cifrado de Feistel .

Ni siquiera necesita una matriz para resolver esta.

Necesita una máscara de bits y un contador.

Inicializar el contador a cero e incrementarlo en llamadas sucesivas. XOR el contador con la máscara de bits (seleccionada aleatoriamente 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 más ancha que 9 bits. (En otras palabras, la máscara de bits es un entero no superior a 511.)

Asegúrese de que cuando el contador pase 1000, usted poner 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.

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

• MP3 reproductor que reproduce cada canción al azar, pero solo una vez por álbum/directorio
• Pixel wise fotogramas de vídeo efecto de disolución (rápido y suave)
• Creando una imagen de niebla secreta de "ruido" para firmas y marcadores (esteganografía)
• ID de objetos de datos para serialización de 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 un nuevo cifrado ubicación en buffer). Esto realmente hizo que los compañeros de criptoanálisis se volvieran locos conmigo: -)
• Texto Plano a Plano Como cifrado de texto Crypt para SMS, correos electrónicos, etc.
• Mi Calculadora de Poker Texas Hold'em (THC)
• Varios de mis juegos para simulaciones," barajar", clasificación
• más

Está abierto, libre. Inténtalo...

Aquí hay un código que escribí que utiliza la lógica de la primera solución. Sé que esto es "agnóstico del lenguaje", pero solo quería presentarlo 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]);
}

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 Números aleatorios no repetitivos serán de complejidad O(n), según sea necesario.
Nota: El azar debe ser estático con la seguridad del hilo aplicada.

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

Otra posibilidad:

Puede usar una matriz de indicadores. Y toma 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 salvaguardia.

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

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

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

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

Aquí hay algunos ejemplos de código COBOL con los que puedes jugar.
Puedo enviarte a RANDGEN.archivo exe para que pueda jugar con él para ver si quiere que usted 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.

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

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

2. Shuffle list A usando Fisher-Yates, toma n tiempo.

3. Al dibujar un número, hacer 1-paso Fisher-Yates barajar en la otra lista.

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

Preproceso

cursor = 0

selector = A
other    = B

shuffle(A)

Draw

temp = selector[cursor]

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

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

return temp

Creo que Generador congruente lineal sería la solución más simple.

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

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

PS el método ya se mencionó, pero el post tiene unas suposiciones erróneas sobre los valores constantes. Las constantes a continuación deberían funcionar bien para su caso

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

X = (1002 * X + 757) mod 1001

La mayoría de las respuestas aquí no garantizan que no devolverán el mismo número dos veces. He aquí 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 asume que después de 1000 otras salidas se permite que un valor se repita, pero que ingenuamente permite que 0 siga inmediatamente después de 0 siempre y cuando ambos aparezcan al final y al comienzo de los conjuntos de 1000. Por el contrario, si bien es posible mantener una distancia de 1000 otros valores entre repeticiones, hacerlo obliga a 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 500 otros valores antes de que un valor se pueda 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;
}

Cuando N es mayor que 1000 y necesita dibujar K muestras aleatorias, podría usar un conjunto que contenga las muestras hasta ahora. Para cada sorteo se utiliza 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 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, mantenga un registro de todos los muestras que aún no se han extraído. Cada sorteo elimina una muestra del conjunto de rechazo.

El otro problema obvio con el muestreo de rechazo es que es O(N) almacenamiento, lo que es una mala noticia si N está en 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 aquí. La esencia del algoritmo de Vitter es que después de cada sorteo, se calcula un salto aleatorio utilizando un cierto distribución que garantice 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 últimos dos
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;
}

La pregunta Cómo se genera eficientemente una lista de K enteros no repetitivos entre 0 y un límite superior N se vincula como un duplicado-y si desea algo que es O(1) por número aleatorio generado (sin coste inicial de O(n))) hay un simple ajuste de la respuesta aceptada.

Cree un mapa vacío desordenado (un mapa vacío ordenado tomará O(log k) por elemento) de entero a entero - en lugar de usar una matriz inicializada. Establecer 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 los elementos r y max del mapa existan en el mapa desordenado. Si no existen crearlos con un valor igual a su índice.
3. Intercambiar elementos r y max
4. Devuelve el elemento max y decrementa max por 1 (si max es negativo has 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 es pospuesto / omitido-pero generará exactamente los mismos números desde el mismo PRNG.

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

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