Números aleatórios únicos (sem repetição) em O (1)?

Eu gostaria de gerar números aleatórios únicos entre 0 e 1000 que nunca se repetem (ou seja, 6 não aparecem duas vezes), mas isso não recorre a algo como uma pesquisa O (N) de valores anteriores para isso. Isso é possível?

Inicialize uma matriz de 1001 números inteiros com os valores 0-1000 e defina uma variável, max, para o índice máximo atual da matriz (começando com 1000). Escolha um número aleatório, r, entre 0 e max, troque o número na posição r pelo número na posição max e retorne o número agora na posição max. Reduza no máximo 1 e continue. Quando max for 0, defina max novamente para o tamanho da matriz - 1 e inicie novamente sem a necessidade de reinicializar a matriz.

Atualização: Embora eu tenha inventado esse método sozinho quando respondi à pergunta, depois de algumas pesquisas, percebo que essa é uma versão modificada de Fisher-Yates conhecida como Durstenfeld-Fisher-Yates ou Knuth-Fisher-Yates. Como a descrição pode ser um pouco difícil de seguir, forneci um exemplo abaixo (usando 11 elementos em vez de 1001):

A matriz começa com 11 elementos inicializados na matriz [n] = n, max começa com 10:

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

A cada iteração, um número aleatório r é selecionado entre 0 e max, a matriz [r] e a matriz [max] são trocadas, a nova matriz [max] é retornada e max é 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|
+--+--+--+--+--+--+--+--+--+--+--+

...

Após 11 iterações, todos os números na matriz foram selecionados, max == 0, e os elementos da matriz são embaralhados:

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

Nesse ponto, o máximo pode ser redefinido para 10 e o processo pode continuar.

Você consegue fazer isso:

1. Crie uma lista, 0..1000.
2. Embaralhe a lista. (Veja Shuffle da Fisher-Yates para uma boa maneira de fazer isso.)
3. Retorne os números em ordem da lista aleatória.

Portanto, isso não requer uma pesquisa de valores antigos a cada vez, mas ainda requer O (N) para o shuffle inicial. Mas, como Nils apontou nos comentários, isso é amortizado O (1).

Use um registro de deslocamento de feedback linear máximo .

É implementável em algumas linhas de C e em tempo de execução faz pouco mais do que alguns testes / ramificações, um pouco de adição e mudança de bits. Não é aleatório, mas engana a maioria das pessoas.

Você pode usar um gerador linear de congruência . Onde m(o módulo) seria o número primo mais próximo maior que 1000. Quando você obtém um número fora do intervalo, basta obter o próximo. A sequência será repetida apenas quando todos os elementos ocorrerem e você não precisar usar uma tabela. Esteja ciente das desvantagens deste gerador (incluindo falta de aleatoriedade).

Você pode usar a criptografia de preservação de formato para criptografar um contador. Seu contador passa de 0 para cima e a criptografia usa uma chave de sua escolha para transformá-la em um valor aparentemente aleatório de qualquer largura e largura desejada. Por exemplo, para o exemplo nesta pergunta: raiz 10, largura 3.

As cifras de bloco normalmente têm um tamanho fixo de bloco de, por exemplo, 64 ou 128 bits. Mas a Criptografia de Preservação de Formato permite que você pegue uma cifra padrão como AES e faça uma cifra de largura menor, de qualquer raio e largura que desejar, com um algoritmo ainda criptograficamente robusto.

É garantido que nunca haverá colisões (porque algoritmos criptográficos criam um mapeamento 1: 1). Também é reversível (um mapeamento bidirecional), para que você possa pegar o número resultante e voltar ao valor do contador que iniciou.

Essa técnica não precisa de memória para armazenar uma matriz aleatória, etc, o que pode ser uma vantagem em sistemas com memória limitada.

O AES-FFX é um método padrão proposto para conseguir isso. Eu experimentei algum código Python básico que é baseado na idéia do AES-FFX, embora não seja totalmente compatível - veja o código Python aqui . Pode, por exemplo, criptografar um contador para um número decimal de 7 dígitos com aparência aleatória ou um número de 16 bits. Aqui está um exemplo de raiz 10, largura 3 (para fornecer um número entre 0 e 999 inclusive), conforme a pergunta:

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 obter diferentes sequências pseudo-aleatórias e não repetidas, altere a chave de criptografia. Cada chave de criptografia produz uma sequência pseudo-aleatória não repetitiva diferente.

Para números baixos como 0 ... 1000, criar uma lista que contenha todos os números e embaralhar é direto. Mas se o conjunto de números para desenhar é muito grande, existe outra maneira elegante: você pode criar uma permutação pseudo-aleatória usando uma chave e uma função hash criptográfica. Veja o seguinte pseudocódigo de exemplo 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;
}

Aqui hashestão apenas algumas funções pseudo-aleatórias arbitrárias que mapeiam uma cadeia de caracteres para um número inteiro possivelmente não assinado. A função randpermé uma permutação de todos os números dentro de 0 ... pow (2, bits) -1, assumindo uma chave fixa. Isso decorre da construção, porque cada passo que altera a variável indexé reversível. Isso é inspirado em uma cifra Feistel .

Você pode usar o meu algoritmo Xincrol descrito aqui:

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

Este é um método algorítmico puro de geração de números aleatórios, mas únicos, sem matrizes, listas, permutações ou carga de CPU pesada.

A versão mais recente também permite definir o intervalo de números. Por exemplo, se eu quiser números aleatórios exclusivos no intervalo de 0-1073741821.

Eu praticamente o usei para

• MP3 player que reproduz todas as músicas aleatoriamente, mas apenas uma vez por álbum / diretório
• Efeito de dissolução de quadros de vídeo com pixel inteligente (rápido e suave)
• Criando um nevoeiro secreto de "ruído" sobre a imagem para assinaturas e marcadores (esteganografia)
• IDs de objeto de dados para serialização de grande quantidade de objetos Java via bancos de dados
• Proteção de bits de memória de maioria tripla
• Criptografia de endereço + valor (cada byte não é apenas criptografado, mas também movido para um novo local criptografado no buffer). Isso realmente deixou os companheiros de criptoanálise loucos comigo :-)
• Texto sem formatação para texto sem criptografia Como criptografia de texto para SMS, e-mails etc.
• Minha calculadora de pôquer Texas Hold`em (THC)
• Vários dos meus jogos para simulações, "embaralhamento", ranking
• Mais

É aberto, grátis. De uma chance...

Você nem precisa de um array para resolver este.

Você precisa de uma máscara de bits e um contador.

Inicialize o contador para zero e aumente-o em chamadas sucessivas. XOR o contador com a máscara de bits (selecionada aleatoriamente na inicialização ou corrigida) para gerar um número aleatório psu. Se você não pode ter números que excedam 1000, não use uma máscara de bits com mais de 9 bits. (Em outras palavras, a máscara de bits é um número inteiro não superior a 511.)

Certifique-se de que quando o contador ultrapassar 1000, você o zere. Nesse momento, você pode selecionar outra máscara de bits aleatória - se desejar - para produzir o mesmo conjunto de números em uma ordem diferente.

Eu acho que o gerador congruencial linear seria a solução mais simples.

e existem apenas três restrições à uma , c e m valores

1. m e c são relativamente primos,
2. a-1 é divisível por todos os fatores primos de m
3. a-1 é divisível por 4 se m é divisível por 4

PS: o método já foi mencionado, mas o post tem suposições erradas sobre os valores constantes. As constantes abaixo devem funcionar bem para o seu caso

No seu caso, você pode usar a = 1002, c = 757,m = 1001

X = (1002 * X + 757) mod 1001

Aqui está um código que digitei que usa a lógica da primeira solução. Eu sei que isso é "independente de idioma", mas só queria apresentar isso como um exemplo em C #, caso alguém esteja procurando uma solução prática 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]);
}

Os resultados desse método são apropriados quando o limite é alto e você deseja gerar apenas alguns números aleatórios.

#!/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";
}

Observe que os números são gerados em ordem crescente, mas você pode embaralhar depois.

Você pode usar um bom gerador de números pseudo-aleatórios com 10 bits e jogar fora de 1001 a 1023 deixando de 0 a 1000.

A partir daqui , obtemos o design para um PRNG de 10 bits.

• 10 bits, polinômio de realimentação x ^ 10 + x ^ 7 + 1 (período 1023)

• use um GalFS LFSR para obter 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 números aleatórios não repetidos terão complexidade O (n), conforme necessário.
Nota: Aleatório deve ser estático com a segurança da linha aplicada.

Digamos que você queira revisar as listas embaralhadas várias vezes, sem ter o O(n)atraso cada vez que você começar a embaralhá-las novamente, nesse caso, podemos fazer o seguinte:

1. Crie 2 listas A e B, de 0 a 1000, ocupa 2nespaço.

2. A lista aleatória A usando Fisher-Yates leva ntempo.

3. Ao desenhar um número, embarque Fisher-Yates em uma etapa na outra lista.

4. Quando o cursor estiver no final da lista, alterne para a outra lista.

Pré-processo

cursor = 0

selector = A
other    = B

shuffle(A)

Desenhar

temp = selector[cursor]

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

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

return temp

A pergunta Como você gera com eficiência uma lista de K números inteiros que não se repetem entre 0 e um limite superior N é vinculada como duplicada - e se você deseja algo que seja O (1) por número aleatório gerado (sem O (n) custo de inicialização)), há um simples ajuste na resposta aceita.

Crie um mapa não ordenado vazio (um mapa ordenado vazio terá O (log k) por elemento) de inteiro para inteiro - em vez de usar uma matriz inicializada. Defina max como 1000 se esse for o máximo,

1. Escolha um número aleatório, r, entre 0 e máx.
2. Assegure-se de que ambos os elementos re e max existam no mapa não ordenado. Se eles não existirem, crie-os com um valor igual ao seu índice.
3. Elementos de troca re max
4. Retorne o elemento max e diminua max em 1 (se max for negativo, você estará pronto).
5. Voltar ao passo 1.

A única diferença em comparação com o uso de uma matriz inicializada é que a inicialização dos elementos é adiada / ignorada - mas gerará exatamente os mesmos números do mesmo PRNG.

Outra possibilidade:

Você pode usar uma matriz de sinalizadores. E pegue o próximo quando ele já estiver escolhido.

Porém, tenha cuidado após 1000 chamadas, a função nunca terminará; portanto, você deve fazer uma salvaguarda.

Aqui está um exemplo de código COBOL com o qual você pode brincar.
Posso enviar o arquivo RANDGEN.exe para que você possa brincar com ele para ver se ele deseja.

   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.

A maioria das respostas aqui não garante que elas não retornem o mesmo número duas vezes. Aqui está uma solução correta:

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

Não tenho certeza de que a restrição esteja bem especificada. Supõe-se que após 1000 outras saídas é permitido repetir um valor, mas que ingenuamente permite que 0 siga imediatamente após 0, desde que ambos apareçam no final e no início dos conjuntos de 1000. Por outro lado, enquanto é possível manter uma distância de Milhares de outros valores entre repetições, o que força uma situação em que a sequência se repete exatamente da mesma maneira todas as vezes, porque não há outro valor que tenha ocorrido fora desse limite.

Aqui está um método que sempre garante pelo menos 500 outros valores antes que um valor possa ser repetido:

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

Quando N for maior que 1000 e você precisar desenhar K amostras aleatórias, poderá usar um conjunto que contenha as amostras até o momento. Para cada sorteio, você usa amostragem por rejeição , que será uma operação "quase" O (1), portanto, o tempo total de execução é quase O (K) com armazenamento O (N).

Esse algoritmo entra em colisão quando K está "próximo" de N. Isso significa que o tempo de execução será muito pior que O (K). Uma correção simples é reverter a lógica para que, para K> N / 2, você mantenha um registro de todas as amostras que ainda não foram desenhadas. Cada sorteio remove uma amostra do conjunto de rejeição.

O outro problema óbvio com a amostragem por rejeição é que é o armazenamento de O (N), o que é uma má notícia se N estiver na casa dos bilhões ou mais. No entanto, existe um algoritmo que resolve esse problema. Este algoritmo é chamado algoritmo de Vitter depois de ser inventor. O algoritmo é descrito aqui . A essência do algoritmo de Vitter é que, após cada sorteio, você calcula um salto aleatório usando uma certa distribuição que garante amostragem 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]

Na verdade, é O (n-1), pois você só precisa de uma troca pelos dois últimos.
Isso é 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;
}

Consulte minha resposta em https://stackoverflow.com/a/46807110/8794687

É um dos algoritmos mais simples que têm média complexidade de tempo O ( s log s ), s denotando o tamanho da amostra. Existem também alguns links para algoritmos de tabela de hash cuja complexidade é reivindicada como O ( s ).

Alguém postou "criando números aleatórios no excel". Eu estou usando esse ideal. Crie uma estrutura com 2 partes, str.index e str.ran; Para 10 números aleatórios, crie uma matriz de 10 estruturas. Defina o str.index de 0 a 9 e str.ran para um número aleatório diferente.

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

Classifique a matriz nos valores em arr [i] .ran. O str.index agora está em uma ordem aleatória. Abaixo está o 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 );
}