Уникальные (неповторяющиеся) случайные числа в O (1)?

Вам даже не нужен массив, чтобы решить эту проблему.

Вам нужна битовая маска и счетчик.

Установите счетчик на ноль и увеличивайте его при последующих вызовах. Выполните XOR счетчика с битовой маской (выбираемой случайным образом при запуске или фиксированной) для генерации псевдослучайного числа. Если у вас не может быть чисел, превышающих 1000, не используйте битовую маску шире 9 бит. (Другими словами, битовая маска - это целое число не выше 511.)

Убедитесь, что когда счетчик достигнет 1000, вы сбросите его на ноль. В это время вы можете выбрать другую случайную битовую маску, если хотите получить тот же набор чисел в другом порядке.

Вот набранный мной код, использующий логику первого решения. Я знаю, что это «агностик языка», но просто хотел представить это в качестве примера на C # на случай, если кто-то ищет быстрое практическое решение.

// 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]);
}

Результаты этого метода подходят, когда лимит высок, и вы хотите сгенерировать только несколько случайных чисел.

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

Обратите внимание, что числа генерируются в возрастающем порядке, но потом вы можете перемешать их.

Вы можете использовать хороший генератор псевдослучайных чисел с 10 битами и выбросить от 1001 до 1023, оставив От 0 до 1000.

Из здесь мы получаем дизайн для 10-битного ГПСЧ ..

• 10 бит, полином обратной связи x ^ 10 + x ^ 7 + 1 (период 1023)

• используйте Galois LFSR, чтобы получить быстрый код

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 Неповторяющиеся случайные числа будут иметь сложность O (n), если требуется.
Примечание. Случайное число должно быть статическим с применением потоковой безопасности.

Вот пример кода COBOL, с которым вы можете поиграться.
Я могу отправить вам файл RANDGEN.exe, чтобы вы могли поиграть с ним и посмотреть, действительно ли он вам нужен.

   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.

Предположим, вы хотите повторять перемешанные списки снова и снова, без задержки O(n) каждый раз, когда вы начинаете перемешивать их снова, в этом случае мы можем сделать это:

1. Создание 2 списков A и B от 0 до 1000 занимает 2n пробела.

2. Перемешивание списка A с использованием Fisher-Yates занимает n времени.

3. При рисовании числа проделайте одностадийную перетасовку Фишера-Йейтса для другого списка.

4. Когда курсор находится в конце списка, переключитесь на другой список.

Предварительная обработка

cursor = 0

selector = A
other    = B

shuffle(A)

Рисовать

temp = selector[cursor]

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

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

return temp

Вопрос Как эффективно сгенерировать список из K неповторяющихся целых чисел от 0 до верхней границы N связан как дубликат - и если вам нужно что-то, что составляет O (1) на сгенерированный случайный number (без начальных затрат O (n))) есть простая настройка принятого ответа.

Создайте пустую неупорядоченную карту (пустая упорядоченная карта будет принимать O (log k) на элемент) от целого до целого числа - вместо использования инициализированного массива. Установите max на 1000, если это максимум,

1. Выберите случайное число r от 0 до макс.
2. Убедитесь, что оба элемента карты r и max существуют в неупорядоченной карте. Если они не существуют, создайте для них значение, равное их индексу.
3. Поменять местами элементы r и max
4. Вернуть max элемента и уменьшить max на 1 (если max становится отрицательным, все готово).
5. Вернуться к шагу 1.

Единственная разница по сравнению с использованием инициализированного массива заключается в том, что инициализация элементов откладывается / пропускается, но при этом будут генерироваться точно такие же числа из того же ГПСЧ.

Еще одна возможность:

Вы можете использовать массив флагов. И возьмите следующий, когда он уже выбран.

Но будьте осторожны после 1000 вызовов, функция никогда не завершится, поэтому вы должны принять меры предосторожности.

Большинство ответов здесь не гарантируют, что они не вернут одно и то же число дважды. Вот правильное решение:

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

Я не уверен, что ограничение четко указано. Предполагается, что после 1000 других выходов значение может повторяться, но это наивно позволяет 0 следовать сразу после 0, пока они оба появляются в конце и начале наборов из 1000. И наоборот, хотя можно сохранить расстояние в 1000 других значений между повторениями, что приводит к возникновению ситуации, когда последовательность воспроизводится каждый раз точно так же, потому что за пределами этого предела не было другого значения.

Вот метод, который всегда гарантирует как минимум 500 других значений, прежде чем значение может быть повторено:

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

Когда N больше 1000 и вам нужно нарисовать K случайных выборок, вы можете использовать набор, который пока содержит образцы. Для каждого розыгрыша вы используете выборку отклонения, что будет «почти» операцией O (1). , поэтому общее время работы составляет около O (K) при хранении O (N).

Этот алгоритм сталкивается с коллизиями, когда K "близко" N. Это означает, что время работы будет намного хуже, чем O (K). Простое исправление - изменить логику так, чтобы при K> N / 2 вы регистрировали все образцы, которые еще не были нарисованы. Каждый розыгрыш удаляет образец из набора для отбраковки.

Другая очевидная проблема с выборкой отбраковки заключается в том, что это O (N) хранилище, что является плохой новостью, если N исчисляется миллиардами или более. Однако есть алгоритм, решающий эту проблему. Этот алгоритм получил название алгоритма Виттера по имени его изобретателя. Алгоритм описан здесь . Суть алгоритма Виттера заключается в том, что после каждого розыгрыша вы вычисляете случайный пропуск, используя определенное распределение, которое гарантирует однородную выборку.

Фишер Йейтс

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

На самом деле это O (n-1), так как вам нужен только один своп для последних двух
Это 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;
}

См. Мой ответ на странице https://stackoverflow.com/a/46807110/8794687

Это один из простейших алгоритмов со средней временной сложностью O (s log s), s, обозначающий размер образца. Там также есть ссылки на алгоритмы хэш-таблиц, сложность которых, как утверждается, составляет O (s).

Кто-то написал "создание случайных чисел в excel". Я использую этот идеал. Создайте структуру из 2 частей, str.index и str.ran; Для 10 случайных чисел создайте массив из 10 структур. Установите str.index от 0 до 9 и str.ran на другое случайное число.

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

Отсортируйте массив по значениям в arr [i] .ran. Str.index теперь находится в случайном порядке. Ниже приведен код 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 );
}