Я хотел бы генерировать уникальные случайные числа от 0 до 1000, которые никогда не повторяются (т.е. 6 не отображается дважды), но это не прибегает к чему-то вроде O (N) поиска предыдущих значений Это. Возможно ли это?
Уникальные (не повторяющиеся) случайные числа в O (1)?
Ответ 1
Инициализировать массив из 1001 целых чисел со значениями 0-1000 и установить переменную max в текущий максимальный индекс массива (начиная с 1000). Выберите случайное число, r, между 0 и макс, замените номер в позиции r номером в позиции max и верните номер в положение max. Уменьшение макс. На 1 и продолжение. Когда max равно 0, установите max обратно в размер массива - 1 и начните снова без необходимости повторной инициализации массива.
Update: Хотя я придумал этот метод самостоятельно, когда я ответил на этот вопрос, после некоторых исследований я понял, что это модифицированная версия Fisher-Yates известная как Дурстенфельд-Фишер-Йейтс или Кнут-Фишер-Йейтс. Поскольку описание может быть немного трудным для подражания, я привел пример ниже (используя 11 элементов вместо 1001):
Массив начинается с 11 элементов, инициализированных массивом [n] = n, max начинается с 10:
+--+--+--+--+--+--+--+--+--+--+--+
| 0| 1| 2| 3| 4| 5| 6| 7| 8| 9|10|
+--+--+--+--+--+--+--+--+--+--+--+
^
max
На каждой итерации случайное число r выбирается между 0 и макс, array [r] и array [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 может быть reset до 10, и процесс может продолжаться.
Ответ 2
Вы можете сделать это:
- Создайте список, 0..1000.
- Перемешать список. (См. Fisher-Yates shuffle для хорошего способа сделать это.)
- Возвращает номера по очереди из перетасованного списка.
Таким образом, это не требует поиска старых значений каждый раз, но для первоначального тасования по-прежнему требуется O (N). Но, как заметил Нилс в комментариях, это амортизируется O (1).
Ответ 3
Используйте Максимальный Линейный регистр сдвига обратной связи.
Он реализуется в нескольких строках C и во время выполнения делает немного больше, чем пара тестов/ветвей, небольшое добавление и смещение бит. Это не случайный, но он обманывает большинство людей.
Ответ 4
Вы можете использовать A Linear Congruential Generator. Где m (модуль) будет ближайшим большим, чем 1000. Когда вы получите номер из диапазона, просто получите следующий. Последовательность будет повторяться только после того, как все элементы произойдут, и вам не нужно использовать таблицу. Помните о недостатках этого генератора, хотя (включая отсутствие случайности).
Ответ 5
Вы можете использовать Format-Preserving Encryption для шифрования счетчика. Ваш счетчик просто идет от 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
... ...
Чтобы получить разные неповторяющиеся псевдослучайные последовательности, измените ключ шифрования. Каждый ключ шифрования создает другую неповторяющуюся псевдослучайную последовательность.
Ответ 6
Для низких чисел, таких как 0... 1000, создание списка, содержащего все числа и перетасовки, выполняется прямо. Но если набор чисел, который нужно рисовать, очень велик, там еще один элегантный способ: вы можете построить псевдослучайную перестановку, используя ключ и криптографическую хеш-функцию. См. Следующий псевдо-код примера С++ - 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, обратим. Это вдохновляет шифр Feistel.
Ответ 7
Вам даже не нужен массив для решения этой проблемы.
Вам нужна битовая маска и счетчик.
Инициализируйте счетчик до нуля и увеличивайте его при последовательных вызовах. XOR счетчик с битовой маской (случайным образом выбранным при запуске или фиксированным) для генерации псевдослучайного числа. Если вы не можете иметь числа, превышающие 1000, не используйте битовую маску более, чем 9 бит. (Другими словами, битмаска представляет собой целое число, не превышающее 511.)
Убедитесь, что, когда счетчик проходит 1000, вы reset равны нулю. В это время вы можете выбрать другую случайную битовую маску -— если вам нравится — для создания одного и того же набора чисел в другом порядке.
Ответ 8
Вы можете использовать описанный здесь алгоритм Xincrol:
http://openpatent.blogspot.co.il/2013/04/xincrol-unique-and-random-number.html
Это чистый алгоритмический метод генерации случайных, но уникальных чисел без массивов, списков, перестановок или тяжелой загрузки процессора.
Последняя версия позволяет также устанавливать диапазон чисел, например, если я хочу уникальные случайные числа в диапазоне 0-1073741821.
Я практически использовал его для
- MP3-плеер, который воспроизводит каждую песню произвольно, но только один раз для альбома/каталога
- Эффективный эффект масштабирования видеороликов (быстрый и плавный)
- Создание секретного "шумового" тумана над изображением для подписей и маркеров (стеганография).
- Идентификаторы объектов данных для сериализации огромного количества объектов Java через базы данных
- Защита бит памяти Triple Major
- Шифрование адреса + значения (каждый байт не только зашифрован, но также перемещается в новое зашифрованное местоположение в буфере). Это действительно заставило криптоанализа сумасшедших меня: -)
- Обычный текст для простого, как Crypt Текстовое шифрование для SMS, электронных писем и т.д.
- Мой Texas Hold`em Poker Calculator (THC)
- Несколько моих игр для моделирования, "перетасовка", рейтинг
- более
Открыто, бесплатно. Попробуйте...
Ответ 9
Вот код, который я набрал, который использует логику первого решения. Я знаю, что это "язык агностик", но просто хотел представить это в качестве примера на С#, если кто-то ищет быстрое практическое решение.
// 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]);
}
Ответ 10
Этот результат метода подходит, когда предел высокий, и вы хотите генерировать только несколько случайных чисел.
#!/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";
}
Обратите внимание, что числа генерируются в порядке возрастания, но затем вы можете перетасовать их.
Ответ 11
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), если требуется.
Примечание. Случайное значение должно быть статичным с применением безопасности потока.
Ответ 12
Другая возможность:
Вы можете использовать массив флагов. И возьмите следующий, когда он уже выбран.
Но будьте осторожны после 1000 вызовов, функция никогда не закончится, поэтому вы должны сделать защиту.
Ответ 13
Вы можете использовать хороший генератор псевдослучайных чисел с 10 бит и выбросить 1001 в 1023, оставив от 0 до 1000.
Из здесь мы получаем дизайн для 10-битного PRNG..
-
10 бит, полином обратной связи x ^ 10 + x ^ 7 + 1 (период 1023)
-
используйте Galois LFSR, чтобы получить быстрый код
Ответ 14
Вот пример кода 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.
Ответ 15
Предположим, вы хотите перебирать перетасованные списки снова и снова, без задержки O(n) каждый раз, когда вы начинаете перетасовывать его снова, в этом случае мы можем сделать это:
-
Создайте 2 списка A и B, с 0 до 1000, занимает пространство
2n. -
Список в случайном порядке A, используя Fisher-Yates, занимает
nвремя. -
При рисовании числа сделайте 1-шаг Fisher-Yates в другом списке.
-
Когда курсор находится в конце списка, переключитесь на другой список.
Preprocess
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
Ответ 16
Я думаю, что Линейный конгруэнтный генератор будет самым простым решением.
и есть только 3 ограничения на значения a, c и m
- m и c являются относительно простыми,
- a-1 делится на все простые множители m
- a-1 делится на 4, если m делится на 4
PS метод уже упоминался, но сообщение имеет неправильные предположения о постоянных значениях. Константы ниже должны хорошо работать для вашего случая
В вашем случае вы можете использовать a = 1002, c = 757, m = 1001
X = (1002 * X + 757) mod 1001
Ответ 17
Большинство ответов здесь не гарантируют, что они не вернут одинаковый номер дважды. Здесь правильное решение:
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;
}
Ответ 18
Когда N больше 1000, и вам нужно нарисовать случайные образцы K, вы могли бы использовать набор, содержащий образцы до сих пор. Для каждой ничьей вы используете отбраковку выборки, которая будет "почти" операцией O (1), поэтому общее время работы почти равно O ( K) с памятью O (N).
Этот алгоритм сталкивается с столкновениями, когда K "близок" N. Это означает, что время работы будет намного хуже, чем O (K). Простое исправление заключается в том, чтобы отменить логику так, чтобы при K > N/2 вы сохраняли запись всех образцов, которые еще не были нарисованы. Каждая нить удаляет образец из набора отклонения.
Другая очевидная проблема с выборкой отбраковки заключается в том, что это O (N) -хранилище, что является плохими новостями, если N находится в миллиардах или более. Однако существует алгоритм, который решает эту проблему. Этот алгоритм называется алгоритмом Виттера после его изобретателя. Алгоритм описан здесь. Суть алгоритма Виттера заключается в том, что после каждой ничьей вы вычисляете случайный прогон с использованием определенного распределения, которое гарантирует равномерную выборку.
Ответ 19
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), поскольку вам нужно только один обмен для последних двух Это С#
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;
}
Ответ 20
Вопрос Как эффективно сгенерировать список K неповторяющихся целых чисел между 0 и верхней границей N связан как дубликат - и если вы хотите что-то то есть O (1) на сгенерированное случайное число (без стоимости запуска O (n))) существует простая настройка принятого ответа.
Создайте пустую неупорядоченную карту (пустая упорядоченная карта возьмет O (log k) на элемент) от integer до integer - вместо использования инициализированного массива. Установите max до 1000, если это максимум,
- Выберите случайное число, r, между 0 и макс.
- Убедитесь, что оба элемента карты r и max существуют в неупорядоченной карте. Если они не существуют, создайте их со значением, равным их индексу.
- Элементы замены r и max
- Возвращаемый элемент max и декремент max на 1 (если max отрицательный вы сделали).
- Возврат к шагу 1.
Единственная разница по сравнению с использованием инициализированного массива заключается в том, что инициализация элементов откладывается/пропускается - но она будет генерировать точные номера из того же PRNG.
Ответ 21
Пожалуйста, см. мой ответ на fooobar.com/info/23208/...
Это один из простейших алгоритмов, которые имеют среднюю временную сложность O (s log s), s - размер выборки. Существуют также некоторые ссылки на алгоритмы хеш-таблицы, которые, как утверждается, представляют собой O (s).