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

Я хотел бы генерировать уникальные случайные числа от 0 до 1000, которые никогда не повторяются (т.е. 6 не появляется дважды), но это не прибегает к чему-то вроде поиска O (N) предыдущих значений, чтобы сделать это. Это возможно?

Инициализируйте массив из 1001 целого числа со значениями 0-1000 и установите переменную max для текущего максимального индекса массива (начиная с 1000). Выберите случайное число r от 0 до max, поменяйте местами число в позиции r и число в позиции max и верните число теперь в положение max. Уменьшите максимум на 1 и продолжайте. Когда max равно 0, установите max обратно к размеру массива - 1 и начните заново без необходимости повторной инициализации массива.

Обновление: хотя я и придумал этот метод самостоятельно, когда ответил на вопрос, после некоторых исследований я понял, что это модифицированная версия Фишера-Йетса, известная как Дюрстенфельд-Фишер-Йейтс или Кнут-Фишер-Йейтс. Поскольку описание может быть немного сложным для подражания, я привел пример ниже (используя 11 элементов вместо 1001):

Массив начинается с 11 элементов, инициализированных в массив [n] = n, max начинается с 10:

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

На каждой итерации случайное число r выбирается между 0 и max, массив [r] и массив [max] меняются местами, возвращается новый массив [max] и значение 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|
+--+--+--+--+--+--+--+--+--+--+--+

...

После 11 итераций все числа в массиве были выбраны, max == 0, и элементы массива перемешиваются:

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

На этом этапе max можно сбросить до 10, и процесс можно продолжить.

Ты можешь сделать это:

1. Создайте список, 0..1000.
2. Перемешать список (См. Fisher-Yates shuffle для хорошего способа сделать это.)
3. Вернуть номера по порядку из перемешанного списка.

Так что это не требует поиска старых значений каждый раз, но все равно требует O (N) для начального перемешивания. Но, как отметил Нильс в комментариях, это амортизированный O (1).

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

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

Вы можете использовать линейный конгруэнтный генератор . Где m(модуль) будет ближайшим простым числом больше 1000. Когда вы выберете число из диапазона, просто получите следующее. Последовательность будет повторяться только после того, как все элементы будут выполнены, и вам не нужно будет использовать таблицу. Имейте в виду недостатки этого генератора (в том числе отсутствие случайности).

Вы можете использовать шифрование с сохранением формата для шифрования счетчика. Ваш счетчик просто идет от 0 вверх, и шифрование использует ключ по вашему выбору, чтобы превратить его в, казалось бы, случайное значение любой ширины и радиуса, которое вы хотите. Например, для примера в этом вопросе: основание 10, ширина 3.

Блочные шифры обычно имеют фиксированный размер блока, например, 64 или 128 бит. Но шифрование, сохраняющее формат, позволяет вам взять стандартный шифр, такой как AES, и создать шифр меньшей ширины, любого желаемого радиуса и ширины, с алгоритмом, который все еще криптографически устойчив.

Гарантируется, что никогда не будет коллизий (поскольку криптографические алгоритмы создают отображение 1: 1). Он также обратим (двухстороннее сопоставление), поэтому вы можете взять полученное число и вернуться к значению счетчика, с которого вы начали.

Этот метод не требует памяти для хранения перемешанного массива и т. Д., Что может быть преимуществом в системах с ограниченной памятью.

AES-FFX является одним из предложенных стандартных методов для достижения этой цели. Я экспериментировал с некоторым базовым кодом Python, который основан на идее AES-FFX, хотя и не полностью соответствует - см. Код Python здесь . Он может, например, зашифровать счетчик на случайное 7-значное десятичное число или 16-разрядное число. Вот пример с основанием 10, шириной 3 (чтобы дать число от 0 до 999 включительно) в качестве поставленного вопроса:

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
...   ...

Чтобы получить разные неповторяющиеся псевдослучайные последовательности, измените ключ шифрования. Каждый ключ шифрования создает различную неповторяющуюся псевдослучайную последовательность.

Для младших чисел, таких как 0 ... 1000, создать список, содержащий все числа, и перетасовать его просто. Но если набор чисел для рисования очень большой, есть другой элегантный способ: вы можете построить псевдослучайную перестановку, используя ключ и криптографическую хеш-функцию. Смотрите следующий 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;
}

Вот hashлишь некоторая произвольная псевдослучайная функция, которая отображает строку символов в возможно огромное целое число без знака. Функция randpermпредставляет собой перестановку всех чисел в пределах 0 ... pow (2, бит) -1, предполагая фиксированный ключ. Это следует из конструкции, потому что каждый шаг, который изменяет переменную, indexявляется обратимым. Это вдохновлено шифром Фейстеля .

Вы можете использовать мой алгоритм Xincrol, описанный здесь:

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

Это чисто алгоритмический метод генерации случайных, но уникальных чисел без массивов, списков, перестановок или большой загрузки процессора.

Последняя версия позволяет также установить диапазон чисел, например, если я хочу уникальные случайные числа в диапазоне 0-1073741821.

Я практически использовал его для

• MP3-плеер, который воспроизводит каждую песню случайным образом, но только один раз для каждого альбома / каталога
• Эффект растворения пикселей в пикселях (быстрый и плавный)
• Создание секретного «шумового» тумана над изображением для подписей и маркеров (стеганография)
• Идентификаторы объектов данных для сериализации огромного количества объектов Java через базы данных
• Защита битов памяти Triple Majority
• Шифрование адреса + значения (каждый байт не только зашифрован, но и перемещен в новое зашифрованное место в буфере). Это действительно сделало ребят из криптоанализа злыми на меня :-)
• Простое преобразование текста в обычное шифрование текста для SMS, электронной почты и т. Д.
• Мой Техасский Холдем Покерный Калькулятор (THC)
• Несколько моих игр для симуляторов, "тасования", рейтинга
• Больше

Это открыто, бесплатно. Попробуйте ...

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

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

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

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

Я думаю, что линейный конгруэнтный генератор будет самым простым решением.

и есть только три ограничения на а , с и м значений

1. m и c относительно простые,
2. а-1 делится на все простые множители м
3. a-1 делится на 4, если m делится на 4

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

В вашем случае вы можете использовать a = 1002, c = 757,m = 1001

X = (1002 * X + 757) mod 1001

Вот код, который я набрал, который использует логику первого решения. Я знаю, что это «не зависит от языка», но просто хотел представить это в качестве примера на 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), как требуется.
Примечание: Random должен быть статическим с применением безопасности потока.

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

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

2. Перемешать список А, используя Фишера-Йейтса, требуется nвремя.

3. Рисуя число, сделайте 1-шаговый переход Фишера-Йейтса в другом списке.

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

Preprocess

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) на сгенерированное случайное число (без O (n)») стоимость запуска)) есть простой твик из принятого ответа.

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

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

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

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

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

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

Вот пример кода 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.

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

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 ( ы лог - ы ), ы , обозначающая размер выборки. Там также есть несколько ссылок на алгоритмы хеш-таблиц, сложность которых, как утверждают, равна 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 );
}